数据结构——链表详解

链表

前言

new一个奶黄包：没关系，这条路我陪你走到底

认识链表

单链表结构图

带头单循环链表结构图

双向循环链表结构图

带头双向循环链表结构图

链表特点

• 单链表在内存中，并不是连续存储的（逻辑上连续）。

• 不支持随机访问

• 插入时只需要改变指针指向

• 没有容量的概念

• 可以高效的在任意位置插入&&删除

• 缓存利用率低

链表实现(带头双向循环链表实现)

链表结构体

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

(1) 新建头节点

LTNode* ListInit()//建立头节点
{LTNode* phead = buyListNode(-1); //建立一个带头节点phead->next = phead;      phead->prev = phead;return phead;
}

(2) 建立新节点

LTNode* buyListNode(LTDataType x)//创建内存初始化数据  
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化：注意所对的结构来初始化newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}

(3)尾部插入节点

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

(4)删除节点

void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;  //记录上一个节点LTNode* tailmove =tail->prev;  //记录上一个节点的上一个节点tailmove->next = phead;    phead->prev = tailmove;free(tail);
}

(5)头部插入节点

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyListNode(x); LTNode* first = phead->next;newnode->next = first;first->prev = newnode;first->next = phead;phead->prev = first;
}

(6) 头删节点

void LTPopFront(LTNode* phead)
{assert(phead);  //判断是否有头节点assert(phead->next != NULL);  //判断第一个节点是否存在LTNode* tail = phead->next;LTNode* tailmove = tail->next;tailmove->prev = phead;phead->next = tailmove;tailmove->next = phead;phead->prev = tailmove;free(tail);
}

(7) 寻找节点

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){//printf("找到了");return cur;//返回指针}cur=cur->next; //每次都走到下一个节点直到phead}//printf("找不到");return NULL;
}

(8) pos位置插入节点

void LTInsert(LTNode* pos, LTDataType x)//头插尾插都可以调用这个函数 
{assert(pos);LTNode* newnode = buyListNode(x); //新建一个节点LTNode* prev = pos->prev;   //记录pos位置的前一个节点newnode->next = pos;   //新节点的下一个节点就是pospos->prev = newnode;   //pos位置节点prve就链接后面newnode->prev = prev;prev->next = newnode;
}

(9) 删除pos位置节点

void LTErase(LTNode* pos)  //删除节点
{assert(pos);LTNode* prve = pos->prev;LTNode* next = pos->next;prve->next = next;next->prev = prve;free(pos);
}

(10) 打印链表

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur!= phead){printf("-> %d ",cur->data );cur = cur->next;}}

测试用例

void test1()
{LTNode* ptail = ListInit();LTPushBack(ptail, 1);LTPushBack(ptail, 3);LTPushBack(ptail, 2);LTPushBack(ptail, 4);LTPushBack(ptail, 5);LTPopBack(ptail);LTPrint(ptail);
}