java数据结构源码分析之--LinkedList

柔情只为你懂 2022-04-06 07:10 286阅读 0赞

# **链表结构教学** #

什么是链表：就是一组没有固定规律的存储结构。

物理地址上不在连续。

为了能更好的从代码上了解链表结构我们将分析java的LinkedList集合内容

首先看一下类

**public** **class** LinkedList<E>

**extends** AbstractSequentialList<E>

**implements** List<E>, Deque<E>, Cloneable, java.io.Serializable

由上面可知LinkedList继承一个抽象类和实现了集合接口，并实现了一个接口，就是qeue，对所谓的队列接口，我们都知道队列是先进先出，所以可以使用他的实现类LinkedList来实现队列顺序，比如爬虫时候的数据源表，或者银行的排队系统之类的。

**public** LinkedList() \{

/\*\*

\* Constructs a list containing the elements of the specified

\* collection, in the order they are returned by the collection's

\* iterator.

\* **@param**  c the collection whose elements are to be placed into this list

\* **@throws** NullPointerException if the specified collection is null

\*/

**public** LinkedList(Collection<? **extends** E> c) \{

**this**();

addAll(c);

LinkedList有两个构造参数，其中一个是将一个 集合全部添加到当前创建的集合中，可能大家发现为什么不是像数组那样初始化一个大小呢。原因是数组是必须要地址连续的，所以你创建数组的时候一定要指定一个大小，而链表已经脱离了物理地址的束缚，链表你不需要在关注地址顺序，因为在上层已经实现了记录一个元素的地址，无论这个地址是在哪里。

正是因为LinkedList实现了队列接口，所以可以用作队列使用。

让我看看一个方法，也就是头插法

/\*\*

\* Links e as first element.

\*/

**private** **void** linkFirst(E e) \{

**final** Node<E> f = first;

**final** Node<E> newNode = **new** Node<>(**null**, e, f);

first = newNode;

**if** (f == **null**)

last = newNode;

**else**

f.prev = newNode;

size\++;

modCount\++;

First，是本身类有的一个属性，用来记录第一个元素的，此时将第一个元素赋值给一个新创建的变量，然后在使用Node的构造方法，进行插入，里面的内容就是Node(Node<E> prev, E element, Node<E> next) \{

**this**.item = element;

**this**.next = next;

**this**.prev = prev;

也就是将新加入的元素的next指向，原本的第一个元素，新元素的prev指向空，因为LinkedList使用的是双向链表，所以新加入的元素如果作为头元素，其前一个指向为空，在看f.prev = newNode;

这个赋值，是将原先的头元素的prey指向新的元素，因为是双向链表，

然后size加一，同时first属性也指向了新的node

**public** E getFirst() \{

**final** Node<E> f = first;

**if** (f == **null**)

**throw** **new** NoSuchElementException();

**return** f.item;

直接返回第一个元素

**public** E removeFirst() \{

**final** Node<E> f = first;

**if** (f == **null**)

**throw** **new** NoSuchElementException();

**return** unlinkFirst(f);

这个就是，移除第一个元素，作为队列使用的时候我们就可通过这种方式来移除第一个元素，

**private** E unlinkFirst(Node<E> f) \{

// assert f == first && f != null;

**final** E element = f.item;

**final** Node<E> next = f.next;

f.item = **null**;

f.next = **null**; // help GC

first = next;

**if** (next == **null**)

last = **null**;

**else**

next.prev = **null**;

size\--;

modCount\++;

**return** element;

由上可知，移除第一个元素所用时间就是O(1)真的很方便使用这个做队列还是很不错的。

LinkedList默认插入的数据的方式，是尾插法，

**public** **boolean** add(E e) \{

linkLast(e);

**return** **true**;

源码如下 **void** linkLast(E e) \{

**final** Node<E> l = last;

**final** Node<E> newNode = **new** Node<>(l, e, **null**);

last = newNode;

**if** (l == **null**)

first = newNode;

**else**

l.next = newNode;

size\++;

modCount\++;

接着我们看一个比较重要的方法，就是插入指定索引位置

**public** **void** add(**int** index, E element) \{

checkPositionIndex(index);

**if** (index == size)

linkLast(element);

**else**

linkBefore(element, node(index));

首先检查index是否是正确的索引，接着我们查看index是否等于size，如果等于size，就直接使用尾插法，如果不是，则继续调用首先我们看node方法。

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;

Node方法就是先判断index的值，如果他小于size的二分之一就从前面查，如果大于就从后面查，如果从前面查，我们就获得他的next，也就是要插入的位置，如果是前面的话就是prev的元素

然后开始执行以下方法

**void** linkBefore(E e, Node<E> succ) \{

// assert succ != null;

**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\++;

也就是，将原本的元素的prev给了新元素的prev，然后新元素的next指向原本的元素，原本元素的prev指向新的元素，然后size加一。

所以由此可见指定位置插入要进行大约二分之N-1次操作

java数据结构源码分析之--LinkedList

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构---链表以及LinkedList源码分析

相关【Java容器源码】LinkedList 源码分析

相关源码分析之LinkedList容器

相关【Java源码分析】LinkedList源码分析

相关 Java数据结构源码分析-LinkedList

相关 Java源码分析之LinkedList

相关源码分析之LinkedList

相关 Java LinkedList 源码分析

相关 java数据结构源码分析之--LinkedList

相关 LinkedList源码分析