> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/di-10-zhang-zhan-he-dui-lie/introduction.md).

# 10.2 链表

## 一、概念

（1）数组的线性序是由数组的下标决定的，链表中的顺序是由各对象中的指针所决定的

（2）链表结点结构\
node *prev;*\
*node* next;\
int key;

（3）链表结点\
node *head;*\
*node* nil;//哨兵

（4）对链表的操作\
LIST-SEARCH(L, k)\
LIST-INSERT(L, x)\
LIST-DELETE(L, x)

（5）哨兵是个哑对象，可以简化边界条件

## 二、代码

（1）没有哨兵的情况

```cpp
//链表结点结构
struct node
{
    node *pre;
    node *next;
    int key;
    //构造函数
    node(int x):pre(NULL),next(NULL),key(x){}
};
//链表结构
struct List
{
    node *head;
    List():head(NULL){}
};
//打印
void List_Print(List *L)
{
    node *p = L->head;
    while(p)
    {
        cout<<p->key<<' ';
        p = p->next;
    }
    cout<<endl;
}
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL
node *List_Search(List *L, int k)
{
    node *x = L->head;
    while(x != NULL && x->key!=k)
        x = x->next;
    return x;
}
//插入
void List_Insert(List *L, node *x)
{
    //插入到表的前端
    x->next = L->head;
    if(L->head != NULL)
        L->head->pre = x;
    L->head = x;
    x->pre = NULL;
}
//删除
void List_Delete(List *L, node* x)
{
    if(x->pre != NULL)
        x->pre->next = x->next;
    else
        L->head = x->next;
    if(x->next != NULL)
        x->next->pre = x->pre;
    delete x;
}
```

（2）有哨兵的情况

```cpp
//链表结点结构
struct node
{
    node *pre;
    node *next;
    int key;
    //构造函数
    node(int x):pre(NULL),next(NULL),key(x){}
};
//链表结构
struct List
{
    node *nil;//哨兵
    List()
    {
        nil = new node(0);
        nil->next = nil;
        nil->pre = nil;
    }
};
//打印
void List_Print(List *L)
{
    node *p = L->nil->next;
    while(p != L->nil)
    {
        cout<<p->key<<' ';
        p = p->next;
    }
    cout<<endl;
}
//搜索，找出L中第一个关键字为k的结点，没有则返回NULL
node *List_Search(List *L, int k)
{
    node *x = L->nil->next;
    while(x != L->nil && x->key!=k)
        x = x->next;
    return x;
}
//插入
void List_Insert(List *L, node *x)
{
    //插入到表的前端
    x->next = L->nil->next;
    L->nil->next->pre = x;
    L->nil->next = x;
    x->pre = L->nil;
}
//删除
void List_Delete(List *L, node* x)
{
    x->pre->next = x->next;
    x->next->pre = x->pre;
    delete x;
}
```

[算法导论 10.2-8 用一个指针实现双链表](https://github.com/windmissing/Introduction_to_Algorithms/tree/ce62f5c6a4fdf8de6cf87a2a544f2fbd87d02cc2/Chapter10/10-2/算法导论%2010.2-8%20用一个指针实现双链表)