线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这意味着这些数据元素可以存在内存未被占用的任何位置。在顺序结构中，每个数据元素只需要存储数据元素就可以了。而在链式结构中，除了要存储数据元素，还要存储它的后继元素的存储地址。

我们把存储数据元素的的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的称为指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。而由n个这样的结点组成一个链表，即为线性表的链式存储结构。当链表的每个结点只包含一个指针域时，我们称此链表为单链表。

对于线性表总得有个头有个尾，那么链表也不例外。我们用一个叫做头指针的东西指向链表的第一个结点，对单链表的存取必须从头指针开始进行。由于单链表的最后一个数据元素没有直接后继元素，则指针为空，通常用NULL或^表示。

有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。结节点的数据域可以不存储任何信息。也可以存储例如表长等附加信息，头结点的指针域指向第一个结点，头指针此时指向头结点。

头指针与头节点

头指针与头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。

关于头指针：

在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
头指针具有标识作用，故常用头指针冠以链表的名字。
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

关于头结点：

头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
头结点不是链表所必需的。

单链表带头结点与不带头结点的区别

单链表是一种最为基本的数据结构，常用的单链表又分为带头结点和不带头结点两种。从线性表的定义可以知道，线性表要求允许在任意位置进行插入和删除操作。所有的链表都有一个头指针head，带头结点的链表中head的数据项为空。

带头结点的优点：在第一个结点处插入或删除操作与在其他处插入或删除的操作统一。
不带头结点的优点：节省内存。

下面是带头结点的单链表与空表的比较图。

接下来具体分析。

1.带头结点的插入操作
首先使用临时变量x记录要插入的位置的结点，之后不管要插入的结点o是插到链表头还是插到链表的其他位置都是如下语句:

1
2
3

Node x = 要插入位置的结点; 
o.next = x.next;
x.next = o;

2.不带头结点的插入操作
若要插到链表的开头则

1 2	o.next = head.next; head = o;//这里不再是head.next = x

若插到链表的其他位置则

1 2	o.next = x.next; x.next = o;

3.带头结点的删除操作

1 2	p = 要删除结点的前继结点； p.next = p.next.next;

4.不带头结点的删除操作
删除第一个节点时

1	head=head.next;

删除其他节点时，head的值不会改变。

1	p.next = p.next.next;

综上所述，带头节点的单链表，不论删除和插入的位置如何，不需要修改head的值，不带头结点的单链表则需要修改head的值。所以单链表一般为带头结点的单链表。

单链表的读取

单链表中，若想查找第index个元素，必须从头开始寻找，直到index为止。由于这个算法的时间复杂度取决于index的位置，当index=1时，不需要遍历，第一个就取出数据了。而当index=n时，需要遍历n-1次。因此最坏情况的时间复杂度为O(n)。因为单链表没有定义表长，所以不能事先知道循环多少次，因为也就不方便使用for来控制循环。其核心思想就是指针不断的后移。

private Node getElem(int index) {
    int j = 0;
    Node p = head.next;//指向第一个结点
    while (j < index) {
        p = p.next;
        j++;
    }
    if (j > index)
        // 没有查到，错误提示
    return p;
}

单链表的插入

将结点o插入结点p的后面

1 2	o.next = p.next; p.next = o;

单链表的删除

将结点o删除，o的直接前继为p

1	p.next = o.next;