1.简单链表

与数组一样，链表也是线性结构。不同的是，链表元素并不存储在一个连续的位置，元素之前是用指针链接的

+---+---+   +---+---+   +---+------+ 
| 1 | o---->| 2 | o---->| 3 | NULL |
+---+---+   +---+---+   +---+------+

为什么使用链表？

数组是存储的是同一类型的线性数据，但有以下限制：

• 数组空间是固定的。

• 插入数据和删除数据都非常低效。

  链表优于数组的地方

• 动态大小

• 插入和删除都非常高效且简单

  链表的缺点

• 不支持随机访问（random access）。你要访问元素，就必须从第一个结点开始顺序的遍历整个链表。所以二分查找就无法达到随机访问的效果。

• 列表中的每个元素都要为指针提供额外的空间。

• 对缓存不友好。因为数组是连续的，因此访问局部性（locality of reference）只存在于数组中，而链表这没有这一特性。

  实现

  链表用指向链表的第一个结点表示。第一个结点叫头指针（head）。如果链表为空，头指针的值为 NULL。
  每个结点至少包含两个部分：

• 数据（data）

• 指针（pointer）或引用（reference），用来指向下一结点。

在 C 语言中，可以使用结构来表示一个结点。例如，用 int 表示一个链表结点：

struct Node {
    int data;
    struct Node* next;
}
// 通常使用 typedef 来少些几个字
typedef struct Node node;

在 Java 或 C# 中，LinkedList 可以表示一个类，Node 可以表示为一个单独的类。LinkedList 中包含 Node 的引用：

class LinkedList {
    Node head;
    class Node {
        int data;
        Node next;
        Node(int d) {data = d};
    }
}

代码实现

用 C 实现一个带有三个结点的链表：

// A simple C program to introduce 
// a linked list 
#include <stdio.h> 
#include <stdlib.h> 
struct Node { 
    int data; 
    struct Node* next; 
}; 
// Program to create a simple linked 
// list with 3 nodes 
int main() 
{ 
    struct Node* head = NULL; 
    struct Node* second = NULL; 
    struct Node* third = NULL; 
    // allocate 3 nodes in the heap 
    head = (struct Node*)malloc(sizeof(struct Node)); 
    second = (struct Node*)malloc(sizeof(struct Node)); 
    third = (struct Node*)malloc(sizeof(struct Node)); 
    /* Three blocks have been allocated dynamically. 
    We have pointers to these three blocks as head, 
    second and third     
      head             second         third 
        |              |              |
        |              |              |
    +---+-----+      +----+----+     +----+----+ 
    | # |  #  |      | #  | #  |     | #  |  # |
    +---+-----+      +----+----+     +----+----+ 
# represents any random value. 
Data is random because we haven’t assigned 
anything yet */
    head->data = 1; // assign data in first node 
    head->next = second; // Link first node with 
    // the second node 
    /* data has been assigned to the data part of the first 
    block (block pointed by the head). And next 
    pointer of first block points to second. 
    So they both are linked. 
      head            second           third 
        |             |                |
        |             |                |
    +---+---+     +----+----+     +-----+----+ 
    | 1 | o----->| #  | #  |     | #   | #  | 
    +---+---+     +----+----+     +-----+----+     
*/
    // assign data to second node 
    second->data = 2; 
    // Link second node with the third node 
    second->next = third; 
    /* data has been assigned to the data part of the second 
    block (block pointed by second). And next 
    pointer of the second block points to the third 
    block. So all three blocks are linked. 
      head           second       third 
        |            |            |
        |            |            |
    +---+---+     +---+---+     +----+----+ 
    | 1 | o----->| 2 | o---->| #  | #  | 
    +---+---+     +---+---+     +----+----+
    */
    third->data = 3; // assign data to third node 
    third->next = NULL; 
    /* data has been assigned to data part of third 
    block (block pointed by third). And next pointer 
    of the third block is made NULL to indicate 
    that the linked list is terminated here. 
    We have the linked list ready. 
          head
            | 
            | 
        +---+---+     +---+---+     +----+------+ 
        | 1 | o----->| 2 | o---->| 3  | NULL | 
        +---+---+     +---+---+     +----+------+     
    Note that only head is sufficient to represent 
    the whole list. We can traverse the complete 
    list by following next pointers. */
    return 0; 
}

遍历数组

这里创建一个通用函数（general-purpose function）来遍历链表：

void printList(struct Node* n) 
{
    while(n != NULL) {
        printf("%d ", n->data);
        n = n->next;
    }
}