java什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表(Chain本文所说链表均为单向链表，以下均简称单向链表)实际上是由节点(Node)组成的，一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head)，我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。

这样说可能大家不是很明白，我贴一张图大家可能更容易理解。

那么大家可能清除了，为什么说有了头节点就可以操作所有节点。因为有着不断的引用嘛!

那么在链表里的属性大概就只有两个了：头节点和节点数量。当然，根据需要，我们通常需要更多的属性。

简单的链表可以写为下面的样子：

1 package myChain;

2

3 /**

4 * (单向)链表

5 *

6 * @author Johness

7 */

8 public class PersonChain {

9 private PersonChainNode head; // 头节点

10 private int size; // 链表的实体(即节点的数量)

11 private int modCount; // 链表被操作的次数(备用)

12

13 /**

14 * 获得链表中节点数量

15 *

16 * @return 链表中节点数

17 */

18 public int getSize() {

19 return this.size;

20 }

21

22 /**

23 * 添加节点的一般方法

24 *

25 * @param p

26 * 添加到链表节点的对象 由于实现细节，作为唯一标识，同一个编号的Person只能添加一次

27 */

28 public void addNode(Person p) {

29 if (!contains(p.personNo)) { // 如果链表中没有该对象，则准备添加

30 if (head != null) { // 如果有头节点，则添加新节点作为头节点

31 head = new PersonChainNode((myChain.Person) p, head);

32 size++;

33 modCount++;

34 } else { // 如果没有头节点，则添加对象作为头节点

35 head = new PersonChainNode((myChain.Person) p, null);

36 size++;

37 modCount++;

38 }

39 }

40 }

41 }

以上的代码就是一般链表的骨架了。拥有两个重要属性。