【数据结构】单链表和双向循环链表-阿里云开发者社区

【数据结构】单链表和双向循环链表

2023-10-16 61

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】单链表和双向循环链表

单链表

链表的概念及结构

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

注意：

从上图可以看出，链式结构在逻辑上连续的，但是在物理上不一定连续

现实中的节点一般是从堆上申请出来的

从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续的也可能是不连续

链表的分类

实际中链表的结构非常多样，一下情况组合起来就有8中情况：

单向或者双向

带头或者不带头

循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构：

无头单向非循环链表：结构简单，一般不会用来单独存放数据。实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等。另外这种结构在笔试面试中出现很多
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构带来很多优势，实现反而简单了。

链表的实现

动态申请一个节点

SListNode* BuySListNode(SLTDataType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

创建链表

SListNode* CreateSListNode(int n)
{
  SListNode* phead = NULL, * ptail = NULL;
  for (int i = 0; i < n; i++)
  {
    SListNode* newnode = BuySListNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}

单链表打印

void SListPrint(SListNode* phead)
{
  SListNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

单链表尾插

//尾插要想改变原来的，就要传地址
void SListPushBack(SListNode** pplist, SLTDataType x)
{
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    SListNode* cur = *pplist;
    while (cur->next != NULL)
    {
      cur = cur->next;
    }
    cur->next = newnode;
  }
}

单链表尾删

void SListPopBack(SListNode** pplist)
{
  assert(*pplist);
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    SListNode* ptail = *pplist;
    while (ptail->next->next != NULL)
    {
      ptail = ptail->next;
    }
    free(ptail->next);
    ptail->next = NULL;
  }
}

单链表头插

void SListPushFront(SListNode** pplist, SLTDataType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}

单链表头删

void

注意：在C语言的单链表，关于改变链表的数字的函数传递方式，传的都是地址。如果不传地址的话就不能改变链表的数值。

就如这个例子一样：

void swap(int* a, int* b)
{
  int x = *a;
  *a = *b;
  *b = x;
}
void swap1(int a, int b)
{
  int x = a;
  a = b;
  b = x;
}
int main()
{
  int a = 10;
  int b = 20;
  swap1(a, b);
  printf("a=%d b=%d\n", a, b);
  swap(&a, &b);
  printf("a=%d b=%d\n", a, b);
}

运行结果：

对于第二种方法，传递的是地址，这里直接把地址里面的数字改了

单链表的查找

SListNode* SListFind(SListNode* plist, SLTDataType x)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      printf("找到了\n");
    }
    cur = cur->next;
  }
  printf("找不到\n");
}

单链表在pos位置之后插入x

void SListInsertAfter(SListNode** pplist, SListNode* pos, SLTDataType x)
{
  assert(pos);
  if (*pplist == pos)
  {
    SlistPushFront(pplist, x);
  }
  else
  {
    SListNode* prve = *pplist;
    while (prve->next != pos)
    {
      prve = prve->next;
    }
    SListNode* newnode = BuySListNode(x);
    prve->next = newnode;
    newnode->next = pos;
  }
}

单链表删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SListNode* newNode = pos->next;
    pos->next = newNode->next;
    free(newNode);
  }
}

双向循环链表

初始化

typedef struct ListNode {
  struct ListNode* prve;
  struct ListNode* next;
  LTDataType data;
}LTNode;
LTNode* LTInit() {
  LTNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prve = phead;
  return phead;
}

申请一个新的节点

LTNOde* BuyListNode(LTDatatype x) {
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL) {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->next = NULL;
  node->prve = NULL;
  return node;
}

双向链表的尾插

这个最主要的一部分，就是找到双向链表的尾部。

void LTPushBack(LTNode* phead, LTDataType x) {
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* tail = phead->prve;//tail 现在就是尾指针
  tail->next = newnode;
  newnode->prve = tail;
  newnode->next = phead;
  phead->prve = newnode; 
}

双向链表的尾删

void LTPopBack(LTNode* phead) {
  assert(phead);
  assert(phead->next = phead);
  LTNode* tail = phead->prve;
  LTNode* tailPrve = tail->prve;
  free(tail);
  tailPrve->next = phead;
  phead->prve = tailPrve;
}

思路：找到最后一个节点，然后再通过最后一个节点，找到最后一个的前一个节点。连接起来就可以了。

双向链表的头插

void LTPushFront(LTNode* phead, LTDataType x) {
  LTNode* newnode = BuyListNode(x);
  assert(phead);
  newnode->next = phead->next;
  phead->next->prve = newnode;
  phead->next = newnode;
  newnode->prve = phead;
}

双向链表的头删

思路：先找到第一个然后再找到第二个节点，接着释放掉第一个节点。

void LTPopFront(LTNode* phead) {
  assert(phead);
  assert(phead->next != phead);
  LTNode* first = phead->next;
  LTNode* second = first->next;
  free(first);
  phead->next = second;
  second->prve = phead;
}

顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低	只需要修改指针指向

插入	动态顺序表，空间不够的时候，需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低