LinkList(双向链表实现)

谁践踏了优雅 2021-10-29 10:18 319阅读 0赞

LinkedList是用链表结构存储数据的，比较适合数据的动态插入和删除，随机访问和遍历速度比较慢，还提供了List接口i中没有定义的方法，专门用于操作表头和表尾的元素，所以可以当作堆栈、队列和双向队列来使用。LInkedList持有头节点和尾节点的引用，有两个构造器，一个是无参构造器，另一个是传入外部集合构造器，它没有像ArrayList一样的初始大小的构造器。

1 //集合元素个数
      2 
      3 transient int size = 0;
      4 
      5  
      6 
      7 //头结点引用
      8 
      9 transient Node<E> first;
     10 
     11  
     12 
     13 //尾节点引用
     14 transient Node<E> last;
     15 
     16 //无参构造器
     17 public LinkedList() {} 
     18 
     19 //传入外部集合的构造器
     20 public LinkedList(Collection<? extends E> c) {
     21     this();
     22     addAll(c);
     23 }
     24 
     25 //增(添加)
     26 public boolean add(E e) {
     27   
     28      //在链表尾部添加
     29     linkLast(e);
     30     return true;
     31 }
     32 
     33  
     34 //增(插入)
     35 public void add(int index, E element) {
     36 
     37     checkPositionIndex(index);
     38 
     39     if (index == size) {
     40         //在链表尾部添加
     41         linkLast(element);
     42     } else {
     43         //在链表中部插入
     44         linkBefore(element, node(index));
     45     }
     46 }
     47 
     48  
     49 
     50 //删(给定下标)
     51 public E remove(int index) {
     52 
     53     //检查下标是否合法
     54     checkElementIndex(index);
     55     return unlink(node(index));
     56 }
     57 
     58 //删(给定元素)
     59 public boolean remove(Object o) {
     60     if (o == null) {
     61         for (Node<E> x = first; x != null; x = x.next) {
     62             if (x.item == null) {
     63                 unlink(x);
     64                 return true;
     65             }
     66         }
     67     } else {
     68         //遍历链表
     69         for (Node<E> x = first; x != null; x = x.next) {
     70             if (o.equals(x.item)) {
     71                 //找到了就删除
     72                 unlink(x);
     73                 return true;
     74             }
     75         }
     76     }
     77     return false;
     78 }
     79 
     80  
     81 
     82 //改
     83 public E set(int index, E element) {
     84 
     85     //检查下标是否合法
     86     checkElementIndex(index);
     87 
     88     //获取指定下标的结点引用
     89     Node<E> x = node(index);
     90 
     91     //获取指定下标结点的值
     92 
     93     E oldVal = x.item;
     94 
     95     //将结点元素设置为新的值
     96 
     97     x.item = element;
     98 
     99     //返回之前的值
    100 
    101     return oldVal;
    102 
    103 }
    104 
    105 
    106 //查
    107 public E get(int index) {
    108 
    109     //检查下标是否合法
    110     checkElementIndex(index);
    111 
    112     //返回指定下标的结点的值
    113     return node(index).item;
    114 }

LinkedList的添加元素的方法主要是调用LinkLast和LinkBefore两个方法，LinkLast方法是在链表后面链接一个元素，LinkBefore方法是在链表中间插入一个元素。LinkedList的删除方法通过调用unlink方法将某个元素从链表中移除。下面是链表的插入和删除操作的核心代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //链接到指定结点之前
     2 void linkBefore(E e, Node<E> succ) {
     3 
     4     //获取给定结点的上一个结点引用
     5     final Node<E> pred = succ.prev;
     6 
     7     //创建新结点, 新结点的上一个结点引用指向给定结点的上一个结点
     8     //新结点的下一个结点的引用指向给定的结点
     9     final Node<E> newNode = new Node<>(pred, e, succ);
    10 
    11     //将给定结点的上一个结点引用指向新结点
    12     succ.prev = newNode;
    13 
    14     //如果给定结点的上一个结点为空, 表明给定结点为头结点
    15     if (pred == null) {
    16 
    17         //将头结点引用指向新结点
    18         first = newNode;
    19     } else {
    20         //否则, 将给定结点的上一个结点的下一个结点引用指向新结点
    21         pred.next = newNode;
    22     }
    23 
    24     //集合元素个数加一
    25     size++;
    26 
    27     //修改次数加一
    28     modCount++;
    29 
    30 }
    31 
    32  
    33 
    34 //卸载指定结点
    35 E unlink(Node<E> x) {
    36 
    37     //获取给定结点的元素
    38     final E element = x.item;
    39 
    40     //获取给定结点的下一个结点的引用
    41     final Node<E> next = x.next;
    42 
    43     //获取给定结点的上一个结点的引用
    44     final Node<E> prev = x.prev;
    45 
    46     //如果给定结点的上一个结点为空, 说明给定结点为头结点
    47     if (prev == null) {
    48 
    49         //将头结点引用指向给定结点的下一个结点
    50         first = next;
    51     } else {
    52         //将上一个结点的后继结点引用指向给定结点的后继结点
    53         prev.next = next;
    54         //将给定结点的上一个结点置空
    55         x.prev = null;
    56 
    57     }
    58 
    59     //如果给定结点的下一个结点为空, 说明给定结点为尾结点
    60     if (next == null) {
    61 
    62         //将尾结点引用指向给定结点的上一个结点
    63         last = prev;
    64     } else {
    65 
    66         //将下一个结点的前继结点引用指向给定结点的前继结点
    67         next.prev = prev;
    68         x.next = null;
    69 
    70     }
    71 
    72     //将给定结点的元素置空
    73     x.item = null;
    74 
    75     //集合元素个数减一
    76     size--;
    77     //修改次数加一
    78     modCount++;
    79     return element;
    80 
    81 }

通过源码的分析，对链表的插入和删除的时间复杂度都是O(1)，而对链表的查找和修改操作都需要遍历链表进行元素的定位，这两个操作都是调用的node(int index) 方法定位元素，如下代码演示根据下标来定位元素。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //根据指定位置获取结点
     2 Node<E> node(int index) {
     3     //如果下标在链表前半部分, 就从头开始查起
     4     if (index < (size >> 1)) {
     5         Node<E> x = first;
     6         for (int i = 0; i < index; i++) {
     7             x = x.next;
     8         }
     9         return x;
    10     } else {
    11         //如果下标在链表后半部分, 就从尾开始查起
    12         Node<E> x = last;
    13         for (int i = size - 1; i > index; i--) {
    14             x = x.prev;
    15         }
    16         return x;
    17     }
    18 }

通过下标定位时先判断是在链表的上半部还是下半部

上半部：从头开始找；

下半部：从尾开始找；

因此通过下标的查找和修改操作的时间复杂度是O(n/2)，通过对双向链表的操作还可以实现单项队列，双向队列和栈的功能。

单向队列的操作的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //获取头结点
     2 public E peek() {
     3     final Node<E> f = first;
     4     return (f == null) ? null : f.item;
     5 }
     6  
     7 //获取头结点
     8 public E element() {
     9     return getFirst();
    10 }
    11  
    12 //弹出头结点
    13 public E poll() {
    14     final Node<E> f = first;
    15     return (f == null) ? null : unlinkFirst(f);
    16 }
    17  
    18 //移除头结点
    19 public E remove() {
    20     return removeFirst();
    21 }
    22  
    23 //在队列尾部添加结点
    24 public boolean offer(E e) {
    25     return add(e);
    26 }

双向队列的操作：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //在头部添加
     2 public boolean offerFirst(E e) {
     3     addFirst(e);
     4     return true;
     5 }
     6  
     7 //在尾部添加
     8 public boolean offerLast(E e) {
     9     addLast(e);
    10     return true;
    11 }
    12  
    13 //获取头结点
    14 public E peekFirst() {
    15     final Node<E> f = first;
    16     return (f == null) ? null : f.item;
    17  }
    18  
    19 //获取尾结点
    20 public E peekLast() {
    21     final Node<E> l = last;
    22     return (l == null) ? null : l.item;
    23 }

栈操作：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //入栈
    2 public void push(E e) {
    3     addFirst(e);
    4 }
    5  
    6 //出栈
    7 public E pop() {
    8     return removeFirst();
    9 }

对LindedList，有：

1. LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现

2. LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加

3. LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法

4. LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用

5. 以上分析基于JDK1.7，其他版本会有些出入，因此不能一概而论

以上内容部分借鉴于：https://blog.csdn.net/iteen/article/details/83109717

转载于:https://www.cnblogs.com/Mr-RanX/p/11267016.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/8bb3ba4a757b4733b515f01433e0ea9a.png