链表简介

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相比于线性表顺序结构在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间.同时失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

单链表

单链表中每个结点只包含一个数据域和一个指针.

单链表声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef int T;//元素类型

typedef struct link{
    T data;
    struct link *next;
}SingleLinkList, *PSingleLinkList;

PSingleLinkList Init();

int isEmpty(PSingleLinkList p);

void clearList(PSingleLinkList head);//清空链表

int length(PSingleLinkList head);//返回链表长度

PSingleLinkList append(PSingleLinkList tail, T data);

int insertT(PSingleLinkList head, int pos, T data);

int deleteT(PSingleLinkList head, int pos, T data);

T getValue(PSingleLinkList head, int pos);

int getPos(PSingleLinkList head, T data);

void printSingleList(PSingleLinkList head);

单链表的初始化
链表初始化时生成一个空结点,指针指向这个空结点.
这个空结点不存储数据,只为了在判断边界时更加方便.初始化完成后返回这个结点的头指针.

1
2
3
4
5
6
PSingleLinkList Init(){
    PSingleLinkList head;
    head = (PSingleLinkList)malloc(sizeof(SingleLinkList));
    head->next = NULL;
    return head;
}

判断链表是否为空
只要头结点的后继指针不为空则链表不为空

1
2
3
4
5
6
7
int isEmpty(PSingleLinkList p){
    //只要头结点的后继指针不为空则链表不为空
    if(p->next != NULL){
        return 0;
    }
    return 1;
}

清空链表
清空链表时需要释放对应的内存,顺序是从头结点开始依次释放内存直到指针为空为止.最后再将头指针的后继指针设为空.

释放内存需要两个指针,tmp指针指向要释放的内存位置,next指针指向下一个要释放内存的位置.

1
2
3
4
5
6
7
8
9
10
11
//清空链表
void clearList(PSingleLinkList head){
    PSingleLinkList tmp, next;
    tmp = head->next;
    while(tmp != NULL){
        next = tmp->next;
        free(tmp);
        tmp = next;
    }
    head->next = NULL;
}

返回链表长度

1
2
3
4
5
6
7
8
9
10
//返回链表长度
int length(PSingleLinkList head){
    int i = 0;
    head = head->next;
    while(head != NULL){
        head = head->next;
        i++;
    }
    return i;
}

尾插
在链表尾部插入一个数据

1
2
3
4
5
6
7
8
9
10
11
PSingleLinkList append(PSingleLinkList tail, T data){

    PSingleLinkList tmp;
    tmp = (PSingleLinkList)malloc(sizeof(SingleLinkList));
    if(tmp == NULL){return NULL;}
    tail->next = tmp;
    tmp->data = data;
    tmp->next = NULL;
    tail = tmp;
    return tail;
}

插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//前插法,插入位置必须在原有的链表中,若需要 在末尾插入使用append
int insertT(PSingleLinkList head, int pos, T data){
    PSingleLinkList tmp;
    if(posIsRight(head, pos) == -1){
        return -1;
    }
    for(int i=0; i<pos; i++){
        //要得到要插入位置的前一个指针
        head = head->next;
    }
    tmp = (PSingleLinkList)malloc(sizeof(SingleLinkList));
    tmp->data = data;
    tmp->next = head->next;
    head->next = tmp;
    return 1;
}

删除数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int deleteT(PSingleLinkList head, int pos, T data){
    PSingleLinkList tmp;
    if(posIsRight(head, pos) == -1){
        return -1;
    }
    for(int i=0; i<pos; i++){
        //要得到要删除位置的前一个指针
        head = head->next;
    }
    tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    return 1;

}

获取固定位置的数据

1
2
3
4
5
6
7
8
9
10
11
T getValue(PSingleLinkList head, int pos){
    if(posIsRight(head, pos) == -1){
        return -1;
    }
    for(int i=0; i<pos; i++){
        //要得到要删除位置的前一个指针
        head = head->next;
    }
    head = head->next;
    return head->data;
}

获取数据的位置

1
2
3
4
5
6
7
8
9
10
int getPos(PSingleLinkList head, T data){
    int len = length(head);
    for(int i=0; i<len; i++){
        head = head->next;
        if(head->data == data){
            return i;
        }
    }
    return -1;
}

打印链表

1
2
3
4
5
6
void printSingleList(PSingleLinkList head){
    while(head->next != NULL){
        head = head->next;
        printf("%d\n", head->data);
    }
}

双向链表

循环链表