ToB企服应用市场:ToB评测及商务社交产业平台

标题: LinkedList源码刨析 [打印本页]

---

作者: 一给    时间: 2022-8-27 01:34
标题: LinkedList源码刨析

数组和结点这两种数据结构之间的差异，决定了LinkedList相比ArrayList拥有更高的插入和删除效率，而随机访问效率不如ArrayList。



目录

• transient
  
• Externalizable
  
• LinkedList源码刨析
  
  
  
  • Node
    
  • LinkedList
    
  
  

transient

transient只能用来修饰成员变量（field），被transient修饰的成员变量不参与序列化过程。
序列化: JVM中的Java对象转化为字节序列。
反序列化: 字节序列转化为JVM中的Java对象。
静态成员变量即使不加transient关键字也无法被序列化。

Externalizable

自定义序列化，无视transient关键字

1. public class Person implements Externalizable {
2.     private String nickName;
3.     private transient String realName;
4.    
5.     @Override
6.     public void writeExternal(ObjectOutput out) throws IOException {
7.         out.writeUTF(realName);
8.         out.writeUTF(childName);
9.     }
11.     @Override
12.     public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
13.         realName = in.readUTF();
14.         childName = in.readUTF();
15.     }
16.    
17.     public static void main(String[] args){
18.         //序列化
19.         os = new ObjectOutputStream(new FileOutputStream(filePath));
20.         os.writeObject(x);
21.         //反序列化
22.         is = new ObjectInputStream(new FileInputStream(filePath));
23.         Person readObject = (Person)is.readObject();
24.     }
25. }

复制代码

LinkedList源码刨析

Node

1. private static class Node<E> {
2.         E item;
3.         Node<E> next;//下一个
4.         Node<E> prev;//前一个
6.         Node(Node<E> prev, E element, Node<E> next) {
7.             this.item = element;
8.             this.next = next;
9.             this.prev = prev;
10.         }
11. }

复制代码

LinkedList

因为存在数据结构基础，不全记录，只记录觉得写的妙的源码和比较经典的源码。
看了一段就知道，LinkedList的核心问题在注意头指针和尾指针的同时，怎么严密的修改前指针和后指针的问题，看前问自己几个问题，怎么添加(删除)头(尾)结点？怎么插入(删除)中间结点(给你个结点你怎么确定它是中间结点还是头尾结点?)？。

1. public class LinkedList<E>
2.     extends AbstractSequentialList<E>
3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
4.    
5.     transient int size = 0;
6.    
7.     transient Node<E> first;
8.    
9.     transient Node<E> last;
10.    
11.     //因为类中只记录了first结点和last结点，通过一次二分可以找到目标结点和first结点比较接近还是last结点比较接近
12.         Node<E> node(int index) {
13.         if (index < (size >> 1)) {
14.             Node<E> x = first;
15.             for (int i = 0; i < index; i++)
16.                 x = x.next;
17.             return x;
18.         } else {
19.             Node<E> x = last;
20.             for (int i = size - 1; i > index; i--)
21.                 x = x.prev;
22.             return x;
23.         }
24.         }
25.    
26.     //如果原头结点为空，则让尾指针指向新结点（头尾重合）；如果原头结点不为空，那么就让原头结点的前指针指向新的头结点
27.     private void linkFirst(E e) {
28.         final Node<E> f = first;
29.         final Node<E> newNode = new Node<>(null, e, f);
30.         first = newNode;
31.         if (f == null)
32.             last = newNode;
33.         else
34.             f.prev = newNode;
35.         size++;
36.         modCount++;
37.     }
38.    
39.     //将原尾节点的后指针指向新的尾节点
40.     void linkLast(E e) {
41.         final Node<E> l = last;
42.         final Node<E> newNode = new Node<>(l, e, null);
43.         last = newNode;
44.         if (l == null)
45.             first = newNode;
46.         else
47.             l.next = newNode;
48.         size++;
49.         modCount++;
50.     }
51.    
52.     //插入到succ结点之前
53.     void linkBefore(E e, Node<E> succ) {
54.         //记录succ的前指针
55.         final Node<E> pred = succ.prev;
56.         //pred<-newNode->succ
57.         final Node<E> newNode = new Node<>(pred, e, succ);
58.         //将prev<-succ修改为newNode<-succ
59.         succ.prev = newNode;
60.         if (pred == null)
61.             //前指针为空，说明succ为头指针，而现在newNode为头指针
62.             first = newNode;
63.         else
64.             //将pred->succ 修改为 pred->newNode
65.             pred.next = newNode;
66.         size++;
67.         modCount++;
68.     }
69.    
70.     //这也有栈顶？peek出的first头节点。
71.     public E peek() {
72.         final Node<E> f = first;
73.         return (f == null) ? null : f.item;
74.     }
75.    
76.     //很粗暴的转换数组
77.     public Object[] toArray() {
78.         Object[] result = new Object[size];
79.         int i = 0;
80.         for (Node<E> x = first; x != null; x = x.next)
81.             result[i++] = x.item;
82.         return result;
83.     }
84.    
85.    
86. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4