[TOC]
### 链表
线性表的另一种实现方式。每个结点不仅不含元素本身的信息，还包含了元素之间的逻辑关系：前驱结点包含了后继结点的信息。
不再支持随机访问，但插入和删除操作比顺序表简单。
因为，物理结构不再连续，需要我们自己去维护结点之间的地址关系。
### 单向链表
#### 定义
在每个结点中除了包含数据域外，还包含了一个指针域，用于指向其后继结点。
类型分为带头结点和不带头结点的链表。
> 单：链表中地址指向为单向。故遍历的方向也是单向。
* 用结构体定义一个结点
```
struct elt {
int data;
struct elt *next;
};
```
* 头结点
不带头结点的单向链表。
我们一般都会将一个结构体指针变量直接指向链表的起始结点，但更多的时候，我们会把头结点封装到一个结构体中，以便于我们存放更多地有关该链表的信息。（如图）
结构体定义为：
```
struct elt {
int data;
struct elt *next;
};
```
* 删除一个结点
```
p->next = p->next->next; //main code
```
* 增加一个结点
```
new->next = p->next;
p->next = new;
```
#### ADT
```
void init(Node *Lp);
void insert(Node L,int data);
int isExist(Node L,int data);
void del(Node L,int data);
void print(Node L);
void destroy(Node L);
Node search(Node L,int data);
Node locate(Node L,int data);
```
#### 代码实现
```
#include <stdio.h>
#include <malloc.h>
/**
* @time:2016/9/6
* @author:j
* @info:the implement of single linked list with head node
*
**/
//the node
struct NodeN{
int data;
struct NodeN *next;
};
typedef struct NodeN *Node;
void init(Node *Lp);
void insert(Node L,int data);
int isExist(Node L,int data);
void del(Node L,int data);
void print(Node L);
void destroy(Node L);
Node search(Node L,int data);
Node locate(Node L,int data);
void init(Node *Lp) {
Node tmp = (struct NodeN *)malloc(sizeof(struct NodeN));
tmp->next = NULL; //empty linked list
tmp->data = -999; //first head
*Lp = tmp;
return;
}
void insert(Node L,int data) {
Node tmp = (struct NodeN *) malloc(sizeof(struct NodeN));
tmp->data = data;
if(L->next == NULL) { // empty
tmp->next = NULL;
L->next = tmp;
} else {
Node p = locate(L,data);
tmp->next = p->next;
p->next = tmp;
}
}
void del(Node L,int data) {
Node tmp = search(L,data);
Node del = tmp->next;
if(NULL != tmp) { //I find it
tmp->next = tmp->next->next;
free(del);
}
}
Node search(Node L,int data) {
Node tmp = L;
while(tmp->next != NULL) {
if(tmp->next->data == data) {
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
Node locate(Node L,int data) {
Node tmp = L;
while(tmp->next != NULL) {
if(tmp->next->data > data) {
return tmp;
}
tmp = tmp->next;
}
return tmp;
}
void print(Node L) {
Node tmp = L->next;
while(tmp!=NULL) {
printf("data is %d\t",tmp->data);
printf("next address is %d",tmp->next);
printf("\n");
tmp = tmp->next;
}
}
void destroy(Node L) {
if(L->next!=NULL)
destroy(L->next);
free(L);
}
int main() {
Node L1;
init(&L1);
insert(L1,10);
insert(L1,5);
insert(L1,8);
del(L1,8);
print(L1);
return 0;
}
```
### 双向链表
#### 定义
单向链表的操作是单向的。我们可以在结点的结构体中增加一条指针。即每个结点都有指向其前驱和后继的两条指针，这样就构成了双向表。
```
struct elt {
int data;
struct elt *next;
struct elt *prior;
};
```
* 增加一个节点
```
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next= p;
p->prior = s;
```
* 删除一个节点
```
p->prior->next = p->next;
p->next->prior = p->prior;
```
#### ADT
```
void init(...);
int *getElement(...);
void delElement(...);
void insertElement(...);
void merge(...); // merge two link lists
void destory(...); // destory a link list.
```
#### 代码实现
```
```
### 循环链表
#### 定义
将单链表中最后一个结点的指针指向第一个元素，整个指针域就构成了一个环，这样，不论从哪个结点出发，都可以找到其余任何元素。我们把这样的表叫做循环表。
而基于单链表构成的循环表，叫做单向循环表。
当然，双向链表也可以构成循环链表，如下图所示。
#### 代码实现
### 静态链表
#### 定义
链表的一种实现方式，即用数组描述链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标CUR。即
```
struct Node {
int data; //data area
int cur; //current
};
typedef struct Node * pNode;
pNode arr[MAXSIZE];
```
#### 代码实现
```
#include <stdio.h>
struct Node {
int data; //data area
int cur; //current
};
typedef struct Node * pNode;
typedef struct Node nodeArr;
//pNode arr[MAXSIZE];
int main() {
}
```
