鏈表定義

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

鏈表的特點(diǎn)：

• 由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多。
• 查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間
• 綜上，插入速度快，查找速度慢。
• 使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間。

鏈表的實(shí)現(xiàn)：

鏈表有很多種不同的類型：?jiǎn)蜗蜴湵?，雙向鏈表以及循環(huán)鏈表。

本文代碼實(shí)現(xiàn)：Java代碼

• 通過內(nèi)部類定義了一個(gè)單向鏈表。
• 以鏈表為底層結(jié)構(gòu)，實(shí)現(xiàn)了一個(gè)棧結(jié)構(gòu)。

棧接口定義：

import java.util.Iterator;

/**
 * 
 * @Created on 2017-02-15 8:40
 * 棧結(jié)構(gòu)定義，定義了基本的6種操作
 */
public interface FlowerStack<T> {

    /**
     * 壓棧
     * @param item
     */
    void push(T item);

    /**
     * 出棧
     * @return
     */
    T pop();

    /**
     * 棧的大小
     * @return
     */
    int size();

    /**
     * 棧是否為空
     * @return
     */
    boolean isEmpty();

    /**
     * 生成迭代器
     */
    Iterator<T> iterator();


}

棧實(shí)現(xiàn)類代碼：

import java.util.Iterator;

/**
 * 
 * @Created on 2017-02-15 19:12
 * 基于鏈表的棧結(jié)構(gòu)
 */
public class FlowerLinkedStack<T> implements FlowerStack<T> {

    private Node<T> first; // 棧頂節(jié)點(diǎn)
    private int length; // 元素?cái)?shù)量

    // 定義一個(gè)內(nèi)部類, 作為鏈表結(jié)構(gòu)
    private class Node<T> {
        T item;
        Node next;
    }

    @Override
    public void push(T item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        length++;
    }

    @Override
    public T pop() {
        if (first == null) {
            return null;
        }
        T item = first.item;
        first = first.next;
        length--;
        return item;
    }

    @Override
    public int size() {
        return length;
    }

    @Override
    public boolean isEmpty() {
        return first == null;
    }

    @Override
    public Iterator<T> iterator() {
        return new FlowerLinkedStackIterator<T>();
    }

    /**
     * 定義一個(gè)迭代器
     * @param <K>
     */
    private class FlowerLinkedStackIterator<K> implements Iterator<K> {

        private Node it = first;

        @Override
        public boolean hasNext() {
            return it != null;
        }

        @Override
        public K next() {
            K next = (K) it.item;
            it = it.next;
            return next;
        }

        @Override
        public void remove() {

        }
    }
}

測(cè)試用例代碼：

import org.junit.Test;

import java.util.Iterator;

/**
 * 
 * @Created on 2017-02-15 19:27
 * 鏈表實(shí)現(xiàn)的棧結(jié)構(gòu) 測(cè)試用例
 */
public class FlowerLinkedStackTest {

    @Test
    public void test() {
        FlowerLinkedStack<Integer> stack = new FlowerLinkedStack();
        System.out.println("初始尺寸：" + stack.size());
        System.out.println("是否為空" + stack.isEmpty());
        System.out.println(stack.pop());
        for(int i=0; i<20; i++) {
            stack.push(i);
            System.out.println("當(dāng)前尺寸：" + stack.size());
            System.out.println("是否為空" + stack.isEmpty());
        }

        System.out.println("-----------------------------------------");

        Iterator<Integer> iterator = stack.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("----------------------------------------");

        for(int i=0; i<30; i++) {
            System.out.println(stack.pop());
            System.out.println("當(dāng)前尺寸：" + stack.size());
            System.out.println("是否為空" + stack.isEmpty());
        }

    }

}