链表设计与实现

什么是链表

链表不同于顺序表，但是得记住顺序表是随机排序，链表的空间不是连续的，而顺序表是连续的。它通过指针来连接一个个分散的节点，虽然物理上不相邻，但是在逻辑上是相邻的。

顺序表他不如链表，本质还是用数组来存的


链表本身分为带头结点的链表和不带头结点，戴头结点的链表就是会有一个头指向后续的整个链表，但是头结点不存放数据。


而不带头结点的链表就像上面那样，第一个节点就是用来存放数据的结点，一般设计链表都会采用带头结点的结构，因为操作更加方便。


那么我们先来写一个链表:

typedef int E;

struct ListNode {
    E element;   //保存当前元素
    struct ListNode * next;   //指向下一个结点的指针
};

typedef struct ListNode * Node;   //这里我们直接为结点指针起别名，可以直接作为表实现

接着我们来编写初始化函数:

void initList(Node head){
    head->next = NULL;   //头结点默认下一个为NULL
}

int main() {
    struct ListNode head;   //这里创建一个新的头结点，头结点不存放任何元素，只做连接，连接整个链表
    initList(&head);  //先进行初始化
}

链表的操作

插入链表

那么链表的插入该如何做到呢？




我们可以先修改新插入的结点和后继结点指向，指向原本在这个位置的结点

按照这个思路，我们来实现一下，首先设计一下函数:

void insertList(Node head, E element, int index){
		//head是头结点，element为待插入元素，index是待插入下标
}

接着我们需要先找到待插入位置的前驱结点：

_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;   //如果插入的位置小于1，那肯定是非法的
    while (--index) {   //通过--index的方式不断向后寻找前驱结点
        head = head->next;   //正常情况下继续向后找
      	if(head == NULL) return 0;  
      	//如果在寻找的过程中发型已经没有后续结点了，那么说明index超出可插入的范围了，也是非法的，直接润
    }
    
    return 1;
}

在循环操作完成后，如果没问题那么会找到对应插入位置的前驱结点，我们只需要按照上面分析的操作来编写代码即可：

_Bool insertList(Node head, E element, int index){
    if(index < 1) return 0;
    while (--index) {
        head = head->next;
      	if(head == NULL) return 0;
    }
    Node node = malloc(sizeof (struct ListNode));
    if(node == NULL) return 0;   //创建一个新的结点，如果内存空间申请失败返回0
    node->element = element;   //将元素保存到新创建的结点中
    node->next = head->next;   //先让新插入的节点指向原本位置上的这个结点
    head->next = node;   //接着将前驱结点指向新的这个结点
    return 1;
}

接下来我们就可以使用打印函数来看一下:

void printList(Node head){
    while (head->next) {
        head = head->next;
        printf("%d ", head->element);   //因为头结点不存放数据，所以从第二个开始打印
    }
}

int main() {
    struct ListNode head;
    initList(&head);
    for (int i = 1; i <=3; ++i) {
        insertList(&head, i * 100, i);   //依次插入3个元素
    }
    printList(&head);   //打印一下看看
}

现在我们来看下结果

删除结点

删除结点的话，我们只需要让该结点的next变为NULL，随之让后继结点指向该删除结点的前继结点即可。








那么我们来根据这样的思路来编写代码，首先是设计删除函数:

void deleteList(Node head, int index){
    //head就是头结点，index依然是待删除的结点位序
}

需要找到待删除结点的前驱结点：

_Bool deleteList(Node head, int index){
    if(index < 1) return 0;   //大体和上面是一样的
    while (--index) {
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;  //注意删除的范围，如果前驱结点的下一个已经是NULL了，那么也说明超过了范围

    return 1;
}

最后就是按照我们上面说的删除结点了:

_Bool deleteList(Node head, int index){
    if(index < 0) return 0;
    while (index--) {
        head = head->next;
        if(head == NULL) return 0;
    }
    if(head->next == NULL) return 0;
    Node tmp = head->next;   //先拿到待删除结点
    head->next = head->next->next;   //直接让前驱结点指向下一个的下一个结点
    free(tmp);   //最后使用free函数释放掉待删除结点的内存
    return 1;
}

这样，我们就成功完成了链表的删除操作

获取链表对应结点的元素

E * getList(Node head, int index){
    if(index < 1) return NULL;   //如果小于0那肯定不合法，返回NULL
    do {
        head = head->next;  //因为不算头结点，所以使用do-while语句
        if(head == NULL) return NULL;  //如果已经超出长度那肯定也不行
    } while (--index);  //到达index就结束
    return &head->element;
}

查找对应元素的位置

int findList(Node head, E element){
    head = head->next;    //先走到第一个结点
    int i = 1;   //计数器
    while (head) {
        if(head->element == element) return i;   //如果找到，那么就返回i
        head = head->next;   //没找到就继续向后看
        i++;   //i记住要自增
    }
    return -1;   //都已经走到链表尾部了，那么就确实没找到了，返回-1
}

求链表的长度

int sizeList(Node head){
    int i = 0;  //从0开始
    while (head->next) {   //如果下一个为NULL那就停止
        head = head->next;
        i++;   //每向后找一个就+1
    }
    return i;
}

链表的性质

效率方面

因为要寻找对应位置的前驱结点，所以链式实现的线性表插入、删除操作的时间复杂度为O(n)，但是不需要做任何的移动操作，效率肯定是比顺序表要高的。

但由于必须要挨个向后寻找，才能找到对应的结点，所以时间复杂度为O(n)，不支持随机访问，只能顺序访问，比顺序表慢。

什么情况下使用顺序表，什么情况下使用链表呢

通过分析顺序表和链表的特性我们不难发现，链表在随机访问元素时，需要通过遍历来完成，而顺序表则利用数组的特性直接访问得到，所以，当我们读取数据多于插入或是删除数据的情况下时，使用顺序表会更好。

而顺序表在插入元素时就显得有些鸡肋了，因为需要移动后续元素，整个移动操作会浪费时间，而链表则不需要，只需要修改结点 指向即可完成插入，所以在频繁出现插入或删除的情况下，使用链表会更好。