java 链表实现栈_java 链表栈

由于栈是先入后出的，使用链表的方式实现栈，时间复杂度都是O（1），以下是一个链表实现栈的例子：

LinkedListStack.java

public class LinkedListStack<E> implements Stack<E> {
 
    private LinkedList<E> list;
 
    public LinkedListStack(){
        list = new LinkedList<>();
    }
 
    @Override
    public int getSize(){
        return list.getSize();
    }
 
    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }
 
    @Override
    public void push(E e){
        list.addFirst(e);
    }
 
    @Override
    public E pop(){
        return list.removeFirst();
    }
 
    @Override
    public E peek(){
        return list.getFirst();
    }
 
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }
 
    public static void main(String[] args) {
 
        LinkedListStack<Integer> stack = new LinkedListStack<>();
 
        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }
 
        stack.pop();
        System.out.println(stack);
    }
}

Stack.java:

public interface Stack<E> {
 
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

LinkedList.java

public class LinkedList<E> {
 
    private class Node{
        public E e;
        public Node next;
 
        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }
 
        public Node(E e){
            this(e, null);
        }
 
        public Node(){
            this(null, null);
        }
 
        @Override
        public String toString(){
            return e.toString();
        }
    }
 
    private Node dummyHead;
    private int size;
 
    public LinkedList(){
        dummyHead = new Node();
        size = 0;
    }
 
    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }
 
    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
 
    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作，练习用：）
    public void add(int index, E e){
 
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
 
        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;
 
        prev.next = new Node(e, prev.next);
        size ++;
    }
 
    // 在链表头添加新的元素e
    public void addFirst(E e){
        add(0, e);
    }
 
    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
 
    // 获得链表的第index(0-based)个位置的元素
    // 在链表中不是一个常用的操作，练习用：）
    public E get(int index){
 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");
 
        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        return cur.e;
    }
 
    // 获得链表的第一个元素
    public E getFirst(){
        return get(0);
    }
 
    // 获得链表的最后一个元素
    public E getLast(){
        return get(size - 1);
    }
 
    // 修改链表的第index(0-based)个位置的元素为e
    // 在链表中不是一个常用的操作，练习用：）
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");
 
        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        cur.e = e;
    }
 
    // 查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }
 
    // 从链表中删除index(0-based)位置的元素, 返回删除的元素
    // 在链表中不是一个常用的操作，练习用：）
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
 
        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;
 
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;
 
        return retNode.e;
    }
 
    // 从链表中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }
 
    // 从链表中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }
 
    // 从链表中删除元素e
    public void removeElement(E e){
 
        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }
 
        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }
 
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
 
        Node cur = dummyHead.next;
        while(cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
 
        return res.toString();
    }
 
}

使用链表实现栈和使用数组实现栈的比较：
1.    使用链表和使用数组实现栈的方式在时间复杂度上都是O（1）级别的
2.    经过测试，使用链表和使用数据实现栈的方式操作耗时是不相伯仲的。
3.    使用数组实现，需要在一定操作之后进行数组空间的重新开辟，使用链表更多体现在new链表节点的实例化上。