个人中心
gpt4 book ai didi

Java集合系列之LinkedList源码分析

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java集合系列之LinkedList源码分析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

上篇我们分析了arraylist的底层实现，知道了arraylist底层是基于数组实现的，因此具有查找修改快而插入删除慢的特点。本篇介绍的linkedlist是list接口的另一种实现，它的底层是基于双向链表实现的，因此它具有插入删除快而查找修改慢的特点，此外，通过对双向链表的操作还可以实现队列和栈的功能。linkedlist的底层结构如下图所示.

Java集合系列之LinkedList源码分析

f表示头结点引用，l表示尾结点引用，链表的每个结点都有三个元素，分别是前继结点引用(p)，结点元素的值(e)，后继结点的引用(n)。结点由内部类node表示，我们看看它的内部结构.

?
1
2
3
4
5
6
7
8
9
10
11
12
//结点内部类
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;
   }
}

node这个内部类其实很简单，只有三个成员变量和一个构造器，item表示结点的值，next为下一个结点的引用，prev为上一个结点的引用，通过构造器传入这三个值。接下来再看看linkedlist的成员变量和构造器.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//集合元素个数
transient int size = 0 ;
 
//头结点引用
transient node<e> first;
 
//尾节点引用
transient node<e> last;
 
//无参构造器
public linkedlist() {}
 
//传入外部集合的构造器
public linkedlist(collection<? extends e> c) {
   this ();
   addall(c);
}

linkedlist持有头结点的引用和尾结点的引用，它有两个构造器，一个是无参构造器，一个是传入外部集合的构造器。与arraylist不同的是linkedlist没有指定初始大小的构造器。看看它的增删改查方法.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//增(添加)
public boolean add(e e) {
   //在链表尾部添加
   linklast(e);
   return true ;
}
 
//增(插入)
public void add( int index, e element) {
   checkpositionindex(index);
   if (index == size) {
     //在链表尾部添加
     linklast(element);
   } else {
     //在链表中部插入
     linkbefore(element, node(index));
   }
}
 
//删(给定下标)
public e remove( int index) {
   //检查下标是否合法
   checkelementindex(index);
   return unlink(node(index));
}
 
//删(给定元素)
public boolean remove(object o) {
   if (o == null ) {
     for (node<e> x = first; x != null ; x = x.next) {
       if (x.item == null ) {
         unlink(x);
         return true ;
       }
     }
   } else {
     //遍历链表
     for (node<e> x = first; x != null ; x = x.next) {
       if (o.equals(x.item)) {
         //找到了就删除
         unlink(x);
         return true ;
       }
     }
   }
   return false ;
}
 
//改
public e set( int index, e element) {
   //检查下标是否合法
   checkelementindex(index);
   //获取指定下标的结点引用
   node<e> x = node(index);
   //获取指定下标结点的值
   e oldval = x.item;
   //将结点元素设置为新的值
   x.item = element;
   //返回之前的值
   return oldval;
}
 
//查
public e get( int index) {
   //检查下标是否合法
   checkelementindex(index);
   //返回指定下标的结点的值
   return node(index).item;
}

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

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

linkbefore和unlink是具有代表性的链接结点和卸载结点的操作，其他的链接和卸载两端结点的方法与此类似，所以我们重点介绍linkbefore和unlink方法.

linkbefore方法的过程图:

Java集合系列之LinkedList源码分析

unlink方法的过程图:

Java集合系列之LinkedList源码分析

通过上面图示看到对链表的插入和删除操作的时间复杂度都是o(1)，而对链表的查找和修改操作都需要遍历链表进行元素的定位，这两个操作都是调用的node(int index)方法定位元素，看看它是怎样通过下标来定位元素的.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//根据指定位置获取结点
node<e> node( int 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;
   }
}

通过下标定位时先判断是在链表的上半部分还是下半部分，如果是在上半部分就从头开始找起，如果是下半部分就从尾开始找起，因此通过下标的查找和修改操作的时间复杂度是o(n/2)。通过对双向链表的操作还可以实现单项队列，双向队列和栈的功能.

单向队列操作:

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

双向队列操作:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//在头部添加
public boolean offerfirst(e e) {
   addfirst(e);
   return true ;
}
 
//在尾部添加
public boolean offerlast(e e) {
   addlast(e);
   return true ;
}
 
//获取头结点
public e peekfirst() {
   final node<e> f = first;
   return (f == null ) ? null : f.item;
  }
 
//获取尾结点
public e peeklast() {
   final node<e> l = last;
   return (l == null ) ? null : l.item;
}

栈操作:

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

不管是单向队列还是双向队列还是栈，其实都是对链表的头结点和尾结点进行操作，它们的实现都是基于addfirst()，addlast()，removefirst()，removelast()这四个方法，它们的操作和linkbefore()和unlink()类似，只不过一个是对链表两端操作，一个是对链表中间操作。可以说这四个方法都是linkbefore()和unlink()方法的特殊情况，因此不难理解它们的内部实现，在此不多做介绍。到这里，我们对linkedlist的分析也即将结束，对全文中的重点做个总结： 1. linkedlist是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现 2. linkedlist无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加 3. linkedlist删除元素后集合占用的内存自动缩小，无需像arraylist一样调用trimtosize()方法 4. linkedlist的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用 5. 以上分析基于jdk1.7，其他版本会有些出入，因此不能一概而论.

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：http://www.cnblogs.com/liuyun1995/p/8287707.html 。

最后此篇关于Java集合系列之LinkedList源码分析的文章就讲到这里了,如果你想了解更多关于Java集合系列之LinkedList源码分析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Struts2框架初学接触
文章推荐： 使用Mybatis对数据库进行单表操作的实现示例
文章推荐： java并发编程之同步器代码示例
文章推荐： java9迁移注意问题总结
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com