数据结构之链表实现栈和队列

爱被打了一巴掌 2022-04-23 19:42 273阅读 0赞

## 链表 ##

**引入**  
前面两篇博客都是用数组实现的栈和队列，数组是一种静态的数据结构，想要实现真正的动态数据结构，就必须要用到链表，链表是一种简单的动态数据结构，它的实现其实就是用到了递归的方式。  
**链表的实现**  
首先写一个私有类进行包装这个节点

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 DummyLinkedList(){
            dummyHead = new Node(null,null);
            size = 0;
        }
    
        //获取链表的元素个数
        public int getSize(){
            return size;
        }
        //返回链表是否为空
        public boolean isEmpty(){
            return size == 0;
        }
    
        //在随机位置插入新元素
        public void add(E e,int index){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("索引错误！");
            }
            //索引0节点前的那个节点
            Node prev = dummyHead;
            for (int i = 0;i < index;i++){
                prev = prev.next;
            }
    
            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;
    //      prev.next = new Node(e,prev.next);
    
            size++;
        }
    
        //在随机位置删除元素
        public E delete(int index){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("索引错误！");
            }
            Node prev = dummyHead;
            Node delNode;
            for (int i = 0;i < index;i++){
                prev = prev.next;
            }
            delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.e;
        }
    	//删除第一个位置的元素
        public E deleteFirst(){
            return delete(0);
        }
    	//删除最后一个位置的元素
        public E deleteLast(){
            return delete(size-1);
        }
    
        //在链表头添加新元素
        public void addFirst(E e){
            add(e,0);
        }
    	//在最后位置添加元素
        public void addLast(E e){
            add(e,size);
        }
    
        //获取链表的某个位置的元素
        public E get(int index){
            if (index < 0 || index > size){
                throw new IllegalArgumentException("索引错误！");
            }
            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);
        }
    
        //修改
        public void set(int index,E e){
            if (index < 0 || index >= size){
                throw new IllegalArgumentException("索引错误！");
            }
            Node cur = dummyHead.next;
            for(int i = 0 ;i < index;i++)
                cur = cur.next;
            cur.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;
        }
    
        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            Node cur = dummyHead.next;
            while (cur != null){
                builder.append(cur + "->");
                cur = cur.next;
            }
            builder.append("NULL");
            return builder.toString();
        }

数组和链表的基本时间复杂度对比  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]  
我们可以得出结论  
1，链表适合在首部操作，数组适合在尾部操作  
2，链表不适合进行查找操作  
3，链表是支持动态扩容，数组的优势是快速查询。

**链表实现栈**

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);
        }
    }

链表实现栈和循环数组实现栈时间上差不多少，因为栈是在一端进行操作  
![在这里插入图片描述][20190408180050941.png]  
**链表实现队列**

public class LinkedListQueue<E> implements Queue<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 head, tail;
        private int size;
    
        public LinkedListQueue(){
            head = null;
            tail = null;
            size = 0;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        @Override
        public boolean isEmpty(){
            return size == 0;
        }
    
        @Override
        public void enqueue(E e){
            if(tail == null){
                tail = new Node(e);
                head = tail;
            }
            else{
                tail.next = new Node(e);
                tail = tail.next;
            }
            size ++;
        }
    
        @Override
        public E dequeue(){
            if(isEmpty())
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    
            Node retNode = head;
            head = head.next;
            retNode.next = null;
            if(head == null)
                tail = null;
            size --;
            return retNode.e;
        }
    
        @Override
        public E getFront(){
            if(isEmpty())
                throw new IllegalArgumentException("Queue is empty.");
            return head.e;
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: front ");
    
            Node cur = head;
            while(cur != null) {
                res.append(cur + "->");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
    
        public static void main(String[] args){
    
            LinkedListQueue<Integer> queue = new LinkedListQueue<>();
            for(int i = 0 ; i < 10 ; i ++){
                queue.enqueue(i);
                System.out.println(queue);
    
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

运行结果可知，循环数组和链表实现队列时间上差不多，但是普通数组在时间上就有很大的差距。  
![在这里插入图片描述][20190408180440336.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220223/7499d29ced2e4705bd8e61fc5328ca76.png
[20190408180050941.png]: /images/20220223/3e5b2b4af259427cba237d0f49b8fb23.png
[20190408180440336.png]: /images/20220223/77cd950f14174256aa016af7848624de.png