本文章原出处：chicago01.top，转载不需说明，随意转载

学习链表前我们得先知道什么是线性表，Wiki Pedia是这样定义线性表的：

线性表（英语：Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。

我们由定义可以很容易联想到我们曾经学过的数组就是一个线性表，而现在新学一个线性表链表 。

[HTML_REMOVED]

链表

我个人把他翻译成链式存储结构，Wiki Pedia是这样定义线性表的：

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

由于不必须按顺序存储，链表在插入的时候可以达到$O(1)$的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要$O(n)$的时间，而顺序表相应的时间复杂度分别是$O(logn)$和$O(1)$。

为什么插入一个数据比顺序表（数组）要快很多呢？(数组是连续的内存)

数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。

我们数组的插入首先要遍历到数组的尾部，得到尾部的下标，然后在尾部后面再插入一个数据。但是链表则是直接在上一个元素后面直接进行插入。

单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

对于单链表，我个人理解是：单向存储读取的链表。链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记 。

主要运用在图的存储上，图的邻接表，通常都是固定顺序访问的。

双向链表

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

呢么对于双向链表的理解：双向存储读取的链表。

定义

value 用于存储权值，*prev指向上一个节点，*next 指向下一个节点。

struct Node{
    int value;
    Node *prev,*next;
};

Node *head,*tail;

初始化双向链表

inline void initialize();               //新键链表
inline void insert(Node *p,int val);    //在 P 后面增加数据val值
inline void remove(Node *p);            //删除 P 
inline void recycle();                  //链表内存回收 

inline void initialize()
{
    head = new Node();
    tail = new Node();
    head->next = tail;
    tail->prev = head;
}

增加一个节点

inline void insert(Node *p,int val)
{
    Node *q = new Node();
    q->value = val;
    p->next->prev = q;
    q->next = p->next;
    p->next = q;
    q->prev = p;
}

删除一个节点

inline void remove(Node *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
}

链表回收

inline void recycle()
{
    while (head != tail)
    {
        head = head->next;
        delete head->prev;
    }
    delete tail;
}

所有代码

struct Node{
    int value;
    Node *prev,*next;
};

Node *head,*tail;

inline void initialize();               //新键链表
inline void insert(Node *p,int val);    //在 P 后面增加数据val值
inline void remove(Node *p);            //删除 P 
inline void recycle();                  //链表内存回收 

inline void initialize()
{
    head = new Node();
    tail = new Node();
    head->next = tail;
    tail->prev = head;
}

inline void insert(Node *p,int val)
{
    Node *q = new Node();
    q->value = val;
    p->next->prev = q;
    q->next = p->next;
    p->next = q;
    q->prev = p;
}

inline void remove(Node *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
}

inline void recycle()
{
    while (head != tail)
    {
        head = head->next;
        delete head->prev;
    }
    delete tail;
}