java什么是链表

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 }

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