一文带你深入了解链表(C)

目录

一、初级

1、概念

2、定义节点结构

3、初始化

4、插入数据

A、创建新节点

B、尾插

C、头插

D、输出

5、删除

A、尾删

B、头删

C、指定删

二、再封装

1、定义链表结构体

2、创建链表和节点

3、数据插入

A、尾插

B、头插

4、删除

A、尾删

B、头删

C、任意删

5、释放

三、无头链表

1、定义结构体

2、创建节点

3、初始化

4、插入

A、尾插

B、头插

5、删除

A、尾删

B、头删

C、任意删

6、打印

一、初级

1、概念

链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

水点字，代码太多了

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

2、定义节点结构

一个数据域，一个指针域，数据域用抽象数据类型

typedef int Elementtype;

//定义节点结构

typedef struct Node

{

Elementtype data;

struct Node* next;

}Node, linklist;

3、初始化

头结点不存储数据

头结点的next指向NULL

void linklist_init(linklist* list)

{

list->data = -1;      //头结点不存储数据

list->next = NULL;    //头结点的next指向NULL

}

4、插入数据

A、创建新节点

Node* createNode(Elementtype val)

{

Node* newNode = calloc(1, sizeof(Node));

assert(newNode);

newNode->data = val;

return newNode;

}

B、尾插

在尾部插入节点

void linklist_pushback(linklist* list, Elementtype val)

{

//创建新节点  

Node* newNode = createNode(val);        

//让尾结点指向新节点

Node* curNode = list;                

while (curNode->next)

{

 curNode = curNode->next;

}

curNode->next = newNode;

}

C、头插

在头部插入节点，并成为新节点

void linklist_pushfront(linklist* list, Elementtype val)

{

Node* newNode = createNode(val);

//先让新节点连上原来的第一个节点

newNode->next = list->next;

//让头结点连接新节点

list->next = newNode;

}

D、输出

从头到尾遍历输出

void linklist_print(linklist* list)

{

Node* curNode = list->next;

while (curNode)

{

 printf("%d ", curNode->data);

 curNode = curNode->next;

}

}

5、删除

A、尾删

记得释放已经删除的节点，并且指针置为空

void linklist_popback(linklist* list)

{

Node* curNode = list;

while( curNode->next && curNode->next->next )

{

 curNode = curNode->next;

}

//curNode->next指向要删除的节点

free(curNode->next);

//curNode指向倒数第二个节点

curNode->next = NULL;

}

B、头删

头结点的下一个节点成为新的头结点

void linklist_popfront(linklist* list)

{

//要删除的节点

Node* delNode = list->next;

if(delNode)

{

 list->next = delNode->next;

 free(delNode);

}

}

C、指定删

先找到元素，再删除

void linklist_removeOne(linklist* list, Elementtype val)

{

Node* curNode = list;

while( curNode->next )

{

 if( curNode->next->data == val )

 {

  break;

 }

 curNode = curNode->next;

}

//保存要删除的节点

Node* delNode = curNode->next;

if(delNode)

{

 //先让前面的节点指向后面的节点

 curNode->next = delNode->next;

 //释放节点

 free(delNode);

}

}

二、再封装

1、定义链表结构体

typedef int Elementtype;

//定义节点结构

typedef struct Node

{

Elementtype data;

struct Node* next;

}Node, linklist;

typedef struct linklist

{

int size;

Node* front;

Node* tail;

}Linklist;

2、创建链表和节点

Node* createNode(Elementtype val)

{

Node* newNode = calloc(1, sizeof(Node));

assert(newNode);

newNode->data = val;

return newNode;

}

Linklist* Linklist_create()

{

Linklist* list = calloc(1, sizeof(Linklist));

assert(list);

list->size = 0;

list->front = list->tail = createNode(-1);     //头结点

return list;

}

3、数据插入

A、尾插

void Linklist_pushback(Linklist* list, Elementtype val)

{

Node* newNode = createNode(val);

list->tail->next = newNode;           //直接让tail->next指向新节点

list->tail = newNode;                 //让尾指针指向新节点

list->size++;

}

B、头插

void Linklist_pushfront(Linklist* list, Elementtype val)

{

Node* newNode = createNode(val);

newNode->next = list->front->next;       //让新节点连上原来的链表

list->front->next = newNode;             //让头结点指向新节点

//判断原来有没有数据节点

if( list->size == 0 )

{

 list->tail = newNode;

}

list->size++;

}

4、删除

A、尾删

void Linklist_popback(Linklist* list)

{

if (list->size == 0)

 return;

Node* curNode = list->front;

while( curNode->next != list->tail )       //一直遍历到尾节点

{

 curNode = curNode->next;

}

free(list->tail);                          //释放最后一个节点

curNode->next = NULL;                      //让倒数第二个节点的next指向空

list->tail = curNode;

list->size--;

}

B、头删

void Linklist_popfront(Linklist* list)

{

if (list->size == 0)

 return;

Node* delNode = list->front->next;

list->front->next = delNode->next;

free(delNode);

if( list->size == 1 )

{

 list->tail = list->front;

}

list->size--;

}

C、任意删

void Linklist_removeOne(Linklist* list, Elementtype val)

{

if (list->size == 0)

 return;

Node* curNode = list->front;

while( curNode->next )

{

 if( curNode->next->data == val )

 {

  break;

 }

 curNode = curNode->next;

}

if( curNode->next )

{

 Node* delNode = curNode->next;

 curNode->next = delNode->next;

       //判断删除的是不是最后一个节点，如果是，更新一下尾指针

       if( delNode->next == NULL )

       {

           list->tail = curNode;

       }

 free(delNode);

 list->size--;

}

}

5、释放

void List_destory(List* list)

{

//删除节点

Node* curNode = list->front;

Node* nextNode = NULL;

while ( curNode )

{

 nextNode = curNode->next;

 free(curNode);

 curNode = nextNode;

}

//释放链表

free(list);

}

三、无头链表

1、定义结构体

typedef int Elementtype;

//定义节点结构

typedef struct Node

{

Elementtype data;

struct Node* next;

}Node;

typedef struct list

{

int size;

Node* front;         //指向第一个数据节点

Node* tail;          //指向最后一个数据节点

}List;

2、创建节点

Node* createNode(Elementtype val)

{

Node* newNode = calloc(1, sizeof(Node));

assert(newNode);

newNode->data = val;

return newNode;

}

3、初始化

void List_init(List* list)

{

list->size = 0;

list->front = list->tail = NULL;

}

4、插入

A、尾插

void List_pushback(List* list, Elementtype val)

{

Node* newNode = createNode(val);

//如果链表为空

if (list->size == 0)  

{

 list->front = list->tail = newNode;

}

else

{

 list->tail->next = newNode;

 list->tail = newNode;

}

list->size++;

}

B、头插

void List_pushfront(List* list, Elementtype val)

{

Node* newNode = createNode(val);

if ( list->size == 0 )

{

 list->front = list->tail = newNode;

}

else

{

 newNode->next = list->front;       //让新节点指向首元节点

 list->front = newNode;             //头指针指向新节点

}

list->size++;

}

5、删除

A、尾删

void List_popback(List* list)

{

if ( list->size == 0 )

{

 return;

}

if( list->size == 1 )

{

 free(list->front);

 list->front = list->tail = NULL;

}

else

{

 Node* curNode = list->front;

 while ( curNode->next != list->tail )

 {

  curNode = curNode->next;

 }

 free(list->tail);

 list->tail = curNode;

 list->tail->next = NULL;

}

list->size--;

}

B、头删

void List_popfront(List* list)

{

if ( list->size == 0 )

{

 return;

}

if ( list->size == 1 )

{

 free(list->front);

 list->front = list->tail = NULL;

}

else

{

 Node* delNode = list->front;

 list->front = delNode->next;

 free(delNode);

}

list->size--;

}

C、任意删

void List_removeOne(List* list, Elementtype val)

{

if ( list->size == 0 )

{

 return;

}

Node* curNode = list->front;

Node* prevNode = NULL;

while ( curNode )

{

 if( curNode->data == val )

 {

  break;

 }

 prevNode = curNode;

 curNode = curNode->next;

}

if( curNode )

{

 if( prevNode )

 {

  prevNode->next = curNode->next;

 }

 free(curNode);

}

list->size--;

}

6、打印

void List_print(List* list)

{

Node* curNode = list->front;

while( curNode )

{

 printf("%d ", curNode->data);

 curNode = curNode->next;

}

}

版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_72157449/article/details/128452073