数据结构中链表及常见操作

1 定义

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

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

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向明上一个或下一个节点的位置的链接（"links"）。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

2 结构

2.1 单向链表

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

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。

2.2 双向链表

每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）

双向链表可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。

2.3 循环链表

在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。指向整个列表的指针可以被称作访问指针。

循环链表中第一个节点之前就是最后一个节点，反之亦然。

3 链表常见用途

 常用于组织删除、检索较少，而添加、遍历较多的数据。

4 链表和数组的区别

 数组在内存中是逐个存放的，也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。而链表则不是，链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域，呈现一种随机的状态。

 数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。而链表则可以，可以动态生成节点并且添加到已有的链表中。

 链表灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操作不灵活，且容易浪费空间，但是时间耗费较小，尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大。

 从内存存储来看，(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦。

附录：（链表的部分常见操作）

1 单向链表

/*线性表的单链表存储结构*/

typedef struct LNode{

  ElemType data;

  struct LNode *next;

}LNode, *LinkList;

/*带有头结点的单链表的基本操作(12个)*/

void InitList(LinkList *L)

{ /* 操作结果：构造一个空的线性表L */

  *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */

  if(!*L) /* 存储分配失败*/

    exit(OVERFLOW);

  (*L)->next=NULL; /* 指针域为空 */

}

void DestroyList(LinkList *L)

{ /* 初始條件：线性表L已存在。操作结果：销毁线性表L */

  LinkList q;

  while(*L)

  {q=(*L)->next;

    free(*L);

    *L=q;

  }

}

void ClearList(LinkList L) /* 不改变L */

{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */

  LinkList p,q;

  p=L->next; /* p指向第一个结点 */

  while(p) /* 没到表尾 */

  {q=p->next;

    free(p);

    p=q;

  }

  L->next=NULL; /* 头结点指针域为空 */

}

Status ListEmpty(LinkList L)

{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */

  return L->next == NULL;

}

int ListLength(LinkList L)

{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */

  int i=0;

  LinkList p=L->next; /* p指向第一个结点 */

  while(p) /* 没到表尾 */

  {

    i++;

    p=p->next;

  }

  return i;

}

Status GetElem(LinkList L,int i,ElemType *e) 

{ /* L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */

  int j=1; /* j为计数器 */

  LinkList p=L->next; /* p指向第一个结点 */

  while(p&&j < i) /* 顺指针向后查找，直到p指向第i个元素或p为空 */

  {

    p=p->next;

    j++;

  }

  if(!p||j>i) /* 第i个元素不存在 */

    return ERROR;

  *e=p->data; /* 取第i个元素 */

  return OK;

}

int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))

{ /* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */

  /* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */

  /*           若这样的数据元素不存在，则返回值为0 */

  int i=0;

  LinkList p=L->next;

  while(p)

  {

    i++;

    if(compare(p->data,e)) /* 找到这样的数据元素 */

      return i;

    p=p->next;

  }

  return 0;

}

Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)

{ /* 初始条件: 线性表L已存在 */

  /* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */

  /*           返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE */

  LinkList q,p=L->next; /* p指向第一个结点 */

  while(p->next) /* p所指结点有后继 */

  {

    q=p->next; /* q为p的后继 */

    if(q->data==cur_e)

    {

      *pre_e=p->data;

      return OK;

    }

    p=q; /* p向后移 */

  }

  return INFEASIBLE;

}

Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)

{ /* 初始条件：线性表L已存在 */

  /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */

  /*           返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */

  LinkList p=L->next; /* p指向第一个结点 */

  while(p->next) /* p所指结点有后继 */

  {

    if(p->data==cur_e)

    {

      *next_e=p->next->data;

      return OK;

    }

    p=p->next;

  }

  return INFEASIBLE;

}

Status ListInsert(LinkList L,int i,ElemType e) 

{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */

  int j=0;

  LinkList p=L,s;

  while(p&&j < i-1) /* 寻找第i-1个结点 */

  {

    p=p->next;

    j++;

  }

  if(!p||j>i-1) /* i小于1或者大于表长 */

    return ERROR;

  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */

  s->data=e; /* 插入L中 */

  s->next=p->next;

  p->next=s;

  return OK;

}

Status ListDelete(LinkList L,int i,ElemType *e) 

{ /* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */

  int j=0;

  LinkList p=L,q;

  while(p->next&&j< i-1) /* 寻找第i个结点，并令p指向其前驱 */

  {

    p=p->next;

    j++;

  }

  if(!p->next||j>i-1) /* 删除位置不合理 */

    return ERROR;

  q=p->next; /* 删除并释放结点 */

  p->next=q->next;

  *e=q->data;

  free(q);

  return OK;

}

void ListTraverse(LinkList L,void(*vi)(ElemType))

/* vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同 */

{ /* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */

  LinkList p=L->next;

  while(p)

  {

    vi(p->data);

    p=p->next;

  }

  printf("\\n");

}

2 双向链表

/* 线性表的双向链表存储结构 */

typedef struct DuLNode

{

  ElemType data;

  struct DuLNode *prior,*next;

}DuLNode,*DuLinkList;

/*带头结点的双向循环链表的基本操作*/

void InitList(DuLinkList *L)

{ /* 产生空的双向循环链表L */

  *L=(DuLinkList)malloc(sizeof(DuLNode));

  if(*L)

(*L)->next=(*L)->prior=*L;

  else

    exit(OVERFLOW);

}

void DestroyList(DuLinkList *L)

{ /* 操作结果：销毁双向循环链表L */

DuLinkList q,p=(*L)->next; /* p指向第一个结点 */

  while(p!=*L) /* p没到表头 */

  {

q=p->next;

    free(p);

    p=q;

  }

  free(*L);

  *L=NULL;

}

void ClearList(DuLinkList L) /* 不改变L */

{ /* 初始条件：L已存在。操作结果：将L重置为空表 */

DuLinkList q,p=L->next; /* p指向第一个结点 */

  while(p!=L) /* p没到表头 */

  {

q=p->next;

    free(p);

    p=q;

  }

L->next=L->prior=L; /* 头结点的两个指针域均指向自身 */

}

Status ListEmpty(DuLinkList L)

{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */

if(L->next==L&&L->prior==L)

    return TRUE;

  else

    return FALSE;

}

int ListLength(DuLinkList L)

{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */

  int i=0;

DuLinkList p=L->next; /* p指向第一个结点 */

  while(p!=L) /* p没到表头 */

  {

    i++;

p=p->next;

  }

  return i;

}

Status GetElem(DuLinkList L,int i,ElemType *e)

{ /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */

  int j=1; /* j为计数器 */

DuLinkList p=L->next; /* p指向第一个结点 */

  while(p!=L&&jnext;

    j++;

  }

if(p==L||j>i) /* 第i个元素不存在 */

    return ERROR;

*e=p->data; /* 取第i个元素 */

  return OK;

}

int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))

{ /* 初始条件：L已存在，compare()是数据元素判定函数 */

  /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */

  /*           若这样的数据元素不存在，则返回值为0 */

  int i=0;

DuLinkList p=L->next; /* p指向第1个元素 */

  while(p!=L)

  {

    i++;

if(compare(p->data,e)) /* 找到这样的数据元素 */

      return i;

p=p->next;

  }

  return 0;

}

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)

{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */

  /*           否则操作失败，pre_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

  while(p!=L) /* p没到表头 */

  {

if(p->data==cur_e)

    {

*pre_e=p->prior->data;

      return TRUE;

    }

p=p->next;

  }

  return FALSE;

}

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)

{ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */

  /*           否则操作失败，next_e无定义 */

DuLinkList p=L->next->next; /* p指向第2个元素 */

  while(p!=L) /* p没到表头 */

  {

if(p->prior->data==cur_e)

    {

*next_e=p->data;

      return TRUE;

    }

p=p->next;

  }

  return FALSE;

}

DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */

{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/

  /* 返回NULL */

  int j;

  DuLinkList p=L; /* p指向头结点 */

if(i<0||i>ListLength(L)) /* i值不合法 */

    return NULL;

for(j=1;j<=i;j++)

p=p->next;

  return p;

}

Status ListInsert(DuLinkList L,int i,ElemType e)

{ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 */

  /* 改进算法2.18，否则无法在第表长+1个结点之前插入元素 */

  DuLinkList p,s;

if(i<1||i>ListLength(L)+1) /* i值不合法 */

    return ERROR;

  p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */

  if(!p) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */

    return ERROR;

  s=(DuLinkList)malloc(sizeof(DuLNode));

  if(!s)

    return OVERFLOW;

s->data=e;

s->prior=p; /* 在第i-1个元素之后插入 */

s->next=p->next;

p->next->prior=s;

p->next=s;

  return OK;

}

Status ListDelete(DuLinkList L,int i,ElemType *e)

{ /* 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长 */

  DuLinkList p;

if(i<1) /* i值不合法 */

    return ERROR;

  p=GetElemP(L,i);  /* 在L中确定第i个元素的位置指针p */

  if(!p) /* p=NULL,即第i个元素不存在 */

    return ERROR;

*e=p->data;

p->prior->next=p->next;//没有考虑链表头？链表尾？

p->next->prior=p->prior;

  free(p);

  return OK;

}

void ListTraverse(DuLinkList L,void(*visit)(ElemType))

{ /* 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit() */

DuLinkList p=L->next; /* p指向头结点 */

  while(p!=L)

  {

visit(p->data);

p=p->next;

  }

  printf("\\n");

}

void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))

{ /* 由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()。另加 */

DuLinkList p=L->prior; /* p指向尾结点 */

  while(p!=L)

  {

visit(p->data);

p=p->prior;

  }

  printf("\\n");

}