LinkedList-链练恋

LinkedList的底层是一个双向链表，在拥有表头的时（表头指向第一个和最后一个元素），对链表的头尾元素增删改查操作效率及高，对链表中间元素的操作相对较慢，因此链表最适合作为队列或栈。

LinkedList的结构

表头结构：

class LinkedList {
transient int size;      // 表示链表长度或者元素个数
transient Node first; // 指向头元素
transient Node last;  // 指向尾元素
}

在源码中可以看到表头结构的first、last和size都增加了transient关键字，transient关键字是用来禁止java对元素序列化的，什么是序列化，序列化是指将对象转化为文件中的字节，这就是序列化，相反为反序列化，序列化可以让代码变成字节，方便写入数据库，或进行网络传输等操作，但同时这些数据的安全性就得不到保障， LinkedList让属性添加transient关键字是为了持有对象的引用，结点中持有前驱结点和后继结点的引用，引用就是对象在内存中的地址值。对于这样的结点形成的链表，序列化这个链表后，结点的前序和后继引用都失效了，因为内存地址变了。这种情况下需要重新连接链表。

结点结构：

class Node {Node prev;   // 指向前一个元素，头元素prev为nullNode next;   // 指向后一个元素，尾元素next为NullE e;            // 存放泛型的具体类型数据
}

源码中LinkedList继承了AbstractSequentialList，AbstractSequentialList提供了基本的对某种结构的接口，在继承AbstractSequentialList后，只需完成部分代码就可以实现一套完整的针对某种结构（例如链表）的操作。LinkedList还实现了Deque接口，Deque接口继承自Queue接口，因此LinkedList可以实现队列的功能。

LinkedList中重要的方法

我们这里只提add 、addFirst方法和removeFirst、removeLast方法，这是对链表或栈操作友好的方法，其他方法一些是add和remove的改装版，一些是对数据不做修改的方法。

add方法 == addLast方法

 public boolean add(E e) {/*情况考虑:1. 当前 LinkedList 有元素LinkedList.last 结点 和新的 Node 结点拼接2. 当前 LinkedList 没有元素a. last = null;b. first = null;*/// 1. 实例化 MyNode 结点对象MyNode node = new MyNode<>(e);// 判断 last 是否为 nullif (null == last) {/*2. 当前添加的结点是整个双向链表中的第一个结点2.1 first 存储当前结点对象当前链表没有元素，链表头 first 和 last 都需要指向当前新结点*/first = node;} else {/*当前链表中有元素，需要对 last 元素进行修改3. 当前链表中有其他结点3.1 首先获取最后一个结点对象，直接使用成员变量 last3.2 修改 last 的 next 指向*/last.setNext(node);// 3.3 修改新添加结点的 prev 为当前 lastnode.setPrev(last);}// last 存储当前新添加结点last = node;// 有效元素个数 + 1size += 1;return true;}

addFirst方法

public void addFirst(E e) {/*情况1. 当前链表中没有元素，first 和 last 直接赋值当前元素2. 当前链表中有其他元素，需要对第一个结点 Node 进行数据修改*/if (null == first) {// 2. 当前 LinkedList 中没有任何元素, 相当于尾插法add(e);} else {// 3. 有其他元素// 3.1 实例化 Node 结点MyNode node = new MyNode<>(e);// 3.2 原本第一个 Node 结点的 prev 赋值为新结点对象first.setPrev(node);// 3.3 当前结点的 Node 结点的 next 赋值为 firstnode.setNext(first);// 3.4 LinkedList 中 first 赋值为新 Node 结点first = node;size += 1;}}

removeFirst方法

 public E removeFirst() {E e = null;if (size > 1) {// 当前 LinkedList 中有结点元素// 1. 获取即将被删除的元素e = first.getE();// 2. 将first指向第二个元素，这时first即为第二个元素first = first.getNext();// 3. 将原先first结点指向第二个元素的指针置为空first.getPrev().setNext(null);// 4. 将first的prev指针指向空first.setPrev(null);// 5. 有效元素 - 1size -= 1;} else if (1 == size) {// 有且只有一个元素，直接获取被删除数据情况，同时 LinkedList first 和 last 同步为 nulle = first.getE();first = null;last = null;size -= 1;}return e;}

removeLast方法

其实和removeFirst方法刚好相反

 public E removeLast() {E e = null;if (size > 1) {// 当前 LinkedList 中有结点元素// 1. 获取即将被删除的元素e = last.getE();// 2. 将last指向倒数第二个元素，这时last即为倒数第二个元素last = last.getPrev();// 3. 将原先last结点指向倒数第二个元素的指针置为空last.getNext().setPrev(null);// 4. 将last的next指针置为空last.setNext(null);// 5. 有效元素 - 1size -= 1;} else if (1 == size) {e = last.getE();first = null;last = null;size -= 1;}return e;}

指针置空顺序不能改变，否则会造成断链，断开的元素还有指针指向，GC不会回收，占用空间。

如有不足，私信或者评论指正，肥肠感激。🙋

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！