链表原理

偏执的太偏执、 2022-07-15 12:18 66阅读 0赞

链表是一种[数据结构][Link 1]，和数组同级。比如，[Java][]中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等等。

一、 单向链表（slist）

链表中最简单的一种是单向链表，每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。如图2就是一个单向链表。

![Center][]

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。   
![这里写图片描述][20160420141138723]   
上图中最左边的节点即为头结点（Head），但是添加节点的顺序是从右向左的，添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用，所以头节点就可以操作所有节点了。   
下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成了一个单向链表。   
![这里写图片描述][20160420134010570]   
节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：

![这里写图片描述][20160420134000174]

[Link 1]: http://lib.csdn.net/base/datastructure
[Java]: http://lib.csdn.net/base/javaee
[Center]: /images/20220715/fbac9dfed78e4feb85e1b2c62dfb41d5.png
[20160420141138723]: /images/20220715/75a8588f4aca476588276a6fc1a85b9f.png
[20160420134010570]: /images/20220715/a05901c2edce43628e4edf5223af1654.png
[20160420134000174]: /images/20220715/a4338bfd80d24b18bee331da0c7b21e3.png