LinkedList双向链表解析

雨点打透心脏的1/2处 2021-09-14 13:38 516阅读 0赞

Queue是队列

![5057999-02fb9054cc6dc02f.png][]

add 增加一个元素  
offer 添加一个元素并返回true 如果队列已满，则返回false  
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
poll 移除并返问队列头部的元素 如果队列为空，则返回null  
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  
peek 返回队列头部的元素 如果队列为空，则返回null

小测试Demo

public static void main(String [] args) {
            Queue<String> queue = new LinkedList<String>();
            //追加元素
            queue.offer("one");
            queue.offer("two");
            queue.offer("three");
            queue.offer("four");
            System.out.println(queue);
            //从队首取出元素并删除
            String poll = queue.poll();
            System.out.println(poll);
            System.out.println(queue);
            //从队首取出元素但是不删除
            String peek = queue.peek();
            System.out.println(peek);
            System.out.println(queue);
            //遍历队列，这里要注意，每次取完元素后都会删除，整个
            //队列会变短，所以只需要判断队列的大小即可
            while(queue.size() > 0) {
                System.out.println(queue.poll());
            }
        }

![5057999-76d6024321421d39.png][]

--------------------

> 双向队列(Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则

public static void main(String [] args) {
            Deque<String> deque = new LinkedList<String>();
            deque.push("a");
            deque.push("b");
            deque.push("c");
            System.out.println(deque);
            //获取栈首元素后，元素不会出栈
            String str = deque.peek();
            System.out.println(str);
            System.out.println(deque);
            while (deque.size() > 0) {
                //获取栈首元素后，元素将会出栈
                System.out.println(deque.pop());
            }
            System.out.println(deque);
        }

![5057999-b0677c54b8e9b79e.png][]

![5057999-36bd301bf480947f.png][]

--------------------

linkedlist和collection关系

![5057999-18235455e8cefa25.png][]

> LinkedList的本质是双向链表。  
> (01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。  
> (02) LinkedList包含两个重要的成员：header 和 size。  
> 　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。  
> 　　size是双向链表中节点的个数。

> LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。既然LinkedList是通过双向链表的，但是它也实现了List接口\{也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”\}。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？  
> 实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。  
> 这就是“双线链表和索引值联系起来”的方法。

183     // 获取双向链表中指定位置的节点
    184     private Entry<E> entry(int index) {
    185         if (index < 0 || index >= size)
    186             throw new IndexOutOfBoundsException("Index: "+index+
    187                                                 ", Size: "+size);
    188         Entry<E> e = header;
    189         // 获取index处的节点。
    190         // 若index < 双向链表长度的1/2,则从前先后查找;
    191         // 否则，从后向前查找。
    192         if (index < (size >> 1)) {
    193             for (int i = 0; i <= index; i++)
    194                 e = e.next;
    195         } else {
    196             for (int i = size; i > index; i--)
    197                 e = e.previous;
    198         }
    199         return e;
    200     }
    
    202     // 从前向后查找，返回“值为对象(o)的节点对应的索引”
    203     // 不存在就返回-1
    204     public int indexOf(Object o) {
    205         int index = 0;
    206         if (o==null) {
    207             for (Entry e = header.next; e != header; e = e.next) {
    208                 if (e.element==null)
    209                     return index;
    210                 index++;
    211             }
    212         } else {
    213             for (Entry e = header.next; e != header; e = e.next) {
    214                 if (o.equals(e.element))
    215                     return index;
    216                 index++;
    217             }
    218         }
    219         return -1;
    220     }

从上面代码我们可以很明显的看出，遍历Linkedlist的时候不要用get方法，他实际上也是调用了entry(index)方法，每一次都会从头或者从尾进行遍历，时间复杂度非常高。

第一个元素（头部）                 最后一个元素（尾部）
            抛出异常        特殊值            抛出异常        特殊值
    插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)
    移除    removeFirst()  pollFirst()      removeLast()    pollLast()
    检查    getFirst()     peekFirst()      getLast()        peekLast()

LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

队列方法       等效方法
    add(e)        addLast(e)
    offer(e)      offerLast(e)
    remove()      removeFirst()
    poll()        pollFirst()
    element()     getFirst()
    peek()        peekFirst()

LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法        等效方法
    push(e)      addFirst(e)
    pop()        removeFirst()
    peek()       peekFirst()

因为是双向链表，header代表头指针，是没有数据的。在头部添加，实质上就是在header和header.next之间添加。在尾部添加，实质上是在header和header.previous之间插入。

24     // 获取LinkedList的第一个元素
     25     public E getFirst() {
     26         if (size==0)
     27             throw new NoSuchElementException();
     28 
     29         // 链表的表头header中不包含数据。
     30         // 这里返回header所指下一个节点所包含的数据。
     31         return header.next.element;
     32     }
     33 
     34     // 获取LinkedList的最后一个元素
     35     public E getLast()  {
     36         if (size==0)
     37             throw new NoSuchElementException();
     38 
     39         // 由于LinkedList是双向链表；而表头header不包含数据。
     40         // 因而，这里返回表头header的前一个节点所包含的数据。
     41         return header.previous.element;
     42     }

54     // 将元素添加到LinkedList的起始位置
     55     public void addFirst(E e) {
     56         addBefore(e, header.next);
     57     }
     58 
     59     // 将元素添加到LinkedList的结束位置
     60     public void addLast(E e) {
     61         addBefore(e, header);
     62     }

/**
         * 将LinkedList当作 LIFO(后进先出)的堆栈
         */
        private static void useLinkedListAsLIFO() {
            System.out.println("\nuseLinkedListAsLIFO");
            // 新建一个LinkedList
            LinkedList stack = new LinkedList();
    
            // 将1,2,3,4添加到堆栈中
            stack.push("1");
            stack.push("2");
            stack.push("3");
            stack.push("4");
            // 打印“栈”
            System.out.println("stack:"+stack);
    
            // 删除“栈顶元素”
            System.out.println("stack.pop():"+stack.pop());
    
            // 取出“栈顶元素”
            System.out.println("stack.peek():"+stack.peek());
    
            // 打印“栈”
            System.out.println("stack:"+stack);
        }
    
        /**
         * 将LinkedList当作 FIFO(先进先出)的队列
         */
        private static void useLinkedListAsFIFO() {
            System.out.println("\nuseLinkedListAsFIFO");
            // 新建一个LinkedList
            LinkedList queue = new LinkedList();
    
            // 将10,20,30,40添加到队列。每次都是插入到末尾
            queue.offer("10");
            queue.offer("20");
            queue.offer("30");
            queue.offer("40");
            // 打印“队列”
            System.out.println("queue:"+queue);
    
            // 删除(队列的第一个元素)
            System.out.println("queue.poll():"+queue.poll());
    
            // 读取(队列的第一个元素)
            System.out.println("queue.peek():"+queue.peek());
    
            // 打印“队列”
            System.out.println("queue:"+queue);
        }

本文大量代码参考自：[https://www.cnblogs.com/skywang12345/p/3308807.html][https_www.cnblogs.com_skywang12345_p_3308807.html]

--------------------

2017.11.28 更新：  
之前电脑是1.8源码，所以我就看了别人的解读做了一部分总结，但刚刚我查看了1.7的源码，发现还是有一些不一样的  
下面代码来自jdk1.7.0\_40  
内部类node相同，都是前后指针和本身

private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

但是全局变量并没有使用头指针header的形式，而是用了first,last两个指针，size表示大小

transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node<E> last;

去掉了头指针，在访问首尾节点更加得方便。  
同时，在按下标访问时，也是比较size的一半，然后从头或者从尾遍历。

Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

[5057999-02fb9054cc6dc02f.png]: /images/20210811/0b4311693fce45838fc60fd606db7c0c.png
[5057999-76d6024321421d39.png]: /images/20210811/1dd706515dbb489c9d198c62ff71f3c7.png
[5057999-b0677c54b8e9b79e.png]: /images/20210811/4099c8b35fc243fa8839087729a5c314.png
[5057999-36bd301bf480947f.png]: /images/20210811/088e860d129140409fd5e96377734b0b.png
[5057999-18235455e8cefa25.png]: /images/20210811/6f1ef00970634d21b48162be678a453f.png
[https_www.cnblogs.com_skywang12345_p_3308807.html]: https://link.jianshu.com?t=https://www.cnblogs.com/skywang12345/p/3308807.html