什么是链表
数据结构里，除了数组之外，最常用的应该就是链表(linked list)了。
那么什么是链表呢，如其名，就是由一个一个的结点(node)连起来的链啦。
所谓结点，是指一个包含有当前节点的值和一个指向下一个节点的链接的实体。
比如在Java中，一个结点的定义可以是这样：
class Node {
// 存放本结点数据的地方
Data data;
// 指向同种类结点的指针
Node next;
// 生成新结点时，指定结点的值
Node (Data d) {
this.data = d;
}
}
一个单向链表包含部分: 当前节点的值和一个指向下一个节点的指针
以上就是一个单向链表(singly linked list)的结点的结构，单向链表就是由一个个这样的结点组成的，链表中的每一个结点都指向下一个节点(next)，每个结点中可以存放任意数据(data)。
还有一种双向链表(Doubly linked list)，其实跟单向链表很像。只不过每个结点既有指向下一个结点的指针，也有指向前一个结点的指针。
链表的实现
构造一个链表其实十分简单，每次生成一个新的结点，然后将当前的结点指向这个新生成的结点。
// 生成结点
Node first = new Node();
Node second = new Node();
Node third = new Node();
// 把结点连起来
first.next = second;
second.next = third;
这样，一个有三个结点的单向链表就实现了。当知道了first，就可以通过first.next访问second，通过first.next.next访问third。
当然以上是为了便于理解，实际上一般应用中，会通过下面的方式构造一个单向链表。
// head指向最开始的那个结点，一旦生成就不会改变
Node head = new Node();
// pointer是一个不断向后移动的指针
Node pointer = head;
// 每生成一个新的结点，pointer指针就向后移动到新生成的结点上
pointer.next = new Node();
pointer = pointer.next;
// 重复以上步骤
pointer.next = new Node();
pointer = pointer.next;
这样，当知道了head结点时，就能通过不断的next访问到后续的所有结点了。
链表的操作
遍历链表
一般只有指向链表第一个结点的head是已知的，通过不断的将指针移动到下一个结点，就能遍历整个链表。
// 遍历整个链表
public void visitLinkedList(Node head) {
// 一般不移动head指针，否则移动之后无法再从头遍历整个链表
Node pointer = head;
while (pointer != null) {
// Do anything you want
pointer = pointer.next;
}
}
插入结点
在链表中插入结点是十分省时的，只需要找到指定的位置，然后新生成一个结点插入即可。
// 在指定的结点(第position个结点)后面插入一个新的结点，新结点的值为data
public void insertNode(Node head, int postion, Data data) {
Node pointer = head;
// 移动到指定结点
for (int i = 0; i < position; i++)
pointer = pointer.next;
// 先将指定结点的后一个结点保存起来
Node tmp = pointer.next;
// 在指定结点后面插入新的结点
pointer.next = new Node(data);
// 将新生成的结点指向原来指定结点的后一个结点
pointer.next.next = tmp;
}
删除结点
删除结点跟插入结点的操作比较类似。
// 删除指定位置的结点
public void deleteNode(Node head, int position) {
Node pointer = head;
// 移动到指定结点的前一个结点
for (int i = 0; i < position - 1; i++)
pointer = pointer.next;
// 直接将指定结点的前一个结点，指向指定结点的后一个结点，
// 类似于指定结点被跳过了，就相当于指定结点删除了
pointer.next = pointer.next.next;
}
总结
其实链表本身的结构还是非常简单的，只不过使用的时候，一定要注意各种操作的先后顺序，否则很容易变成一边捡芝麻，一边丢西瓜的状况（笑。
比如分清，是先进行操作再访问下一个结点，还是先访问下一个结点再进行操作。
// 比如生成一个新的链表，一开始的时候很容易写出下面这样的代码
Node pointer = new Node();
Node head = pointer;
for (int i = 0; i < length; i++) {
pointer = pointer.next;
pointer = new Node();
}
然后发现，咦？为什么我的链表永远都只有一个结点，到底哪里出了问题......
网友评论