数据结构单链表-阿里云开发者社区

单链表

1 链表的概念及结构

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

接次序实现的。

在我们开始讲链表之前，我们是写了顺序表，顺序表就是类似一个数组的东西，它的存放是连续的，优点有很多，比如支持我们随机访问，连续存放，命中率高，区别于单链表我们可以用类似数组的下标进行访问，这大大的提高我们的效率，但是也有缺点，空间不够就要需要扩容，扩容存在消耗的，头部或者中间位置的插入删除，需要挪动，挪动数据也是存在消耗的。避免频繁扩容，一次一般都是按倍数扩容，可能存在空间扩容。

链表的优点：

按需申请空间，不用释放空间。

头部或者中间位置的插入和删除，不需要挪动数据。

不存在空间浪费。

链表的缺陷：

每一个数据，都要存放一个指针去链表后面节点的地址。

不支持随机访问。

链表的结构

typedef int SLNodedataType;
typedef struct SList
{
  SLNodedataType data;
  struct SList* next;
}SLNode;

这个就是我们单链表的基本代码，我们来用图更加清清楚的表示一下它完整的样子。

这就我们基本的逻辑结构，它前一个的next是存放后面的地址的，这样就能找到我们下一个节点。

单链表使用的时候相比和顺序表比较的话，它的使用不会浪费空间，我们需要一个节点就可以开辟一个节点出来供我们使用。但是它存储就不是连续的了。

那我们现在开始写代码来实现单链表。

单链表

首先我们要创建一个结构体。

typedef int SLNodedataType;
typedef struct SList
{
  SLNodedataType data;
  struct SList* next;
}SLNode;

接下来我们首先要打印我们的单链表

在这之前我们应该创建节点，创捷节点很简单，就是按照我们上面的图的前一个存放后面的地址。

//创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;

那下面就是我们的打印单链表。

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

我们来测试一下看看效果。

可以看到我们的单链表也是成功的打印，那接下来就是要写出我们的尾插函数。

写之前我们先来分析分析，首先尾插一个节点进去，那我们是不是要有一个这样的节点，竟然这样就可以写一个创造节点的函数。就叫他CreateSListNode

SLNode* CreateSListNode(SLNodedataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}

写完这个那我们写一个尾插函数，尾插的时候我们要想一想要传什么地址过去，如果是有数据的话其实我们传一级地址就行，但是如果是空的话，就得传二级，因为我们要改变plist的位置。但是也其实是相当于头插，没节点的时候，总不能在空指针后面插入。那我们写一个吧。

void SListPushBcak(SLNode** plist, SLNodedataType x)
{
  SLNode*newnode=CreateSListNode(x);
  assert(plist);
  if (*plist == NULL)
  {
    plist = newnode;
  }
  else
  {
    SLNode* tail = *plist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

看一下我们编译的结果

最后也是成功的尾插进去，那尾插之后就应该要写一个尾删。

写尾删的时候，我们要先考虑怎么找到最后，这和尾插一样，遍历一遍找到最后一个，然后free掉就行了。

代码

void SListPopBack(SLNode** plist)
{
  SLNode* tail = *plist;
  SLNode* prev = NULL;
  while (tail->next != NULL)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
}

这其实就是用了一个双指针的方法找最后一个的前一个，但是我们还需要注意链表不能为空，空了怎么删除啊。所以改进一下。

void SListPopBack(SLNode** plist)
{
  assert(plist);
  assert(*plist);
  SLNode* tail = *plist;
  SLNode* prev = NULL;
  while (tail->next != NULL)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
}

void test1()
{
  //创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  SListPrint(n1);
  SListPushBcak(&n1, 5);
  SListPushBcak(&n1, 6);
  SListPushBcak(&n1, 7);
  SListPushBcak(&n1, 8);
  SListPrint(n1);
  SListPopBack(&n1);
  SListPopBack(&n1);
  SListPrint(n1);
}

不过其实我们也可以不用双指针的办法。

那也整一个玩玩吧

void SListPopBack(SLNode** plist)
{
  assert(plist);
  assert(*plist);
  SLNode* tail = *plist;
  while (tail->next->next != NULL)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;

其实道理是一样的，就是找下下一个的节点是不是为空。

尾插写好就是头插，来吧展示。

void SListPushFront(SLNode** plist, SLNodedataType x)
{
  assert(plist);
  SLNode* newnode = CreateSListNode(x);
  if (*plist == NULL)
  {
    *plist = newnode;
  }
  else
  {
    newnode->next = *plist;
    *plist = newnode;
  }
}

其实想明白也不难，接下来就是头删。

void test1()
{
  //创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  SListPrint(n1);
  SListPushBcak(&n1, 5);
  SListPushBcak(&n1, 6);
  SListPushBcak(&n1, 7);
  SListPushBcak(&n1, 8);
  SListPrint(n1);
  SListPopBack(&n1);
  SListPopBack(&n1);
  SListPrint(n1);
  SListPushFront(&n1, 111);
  SListPushFront(&n1, 222);
  SListPrint(n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPrint(n1);
}

void SListPopFront(SLNode** plist)
{
  assert(plist);
  assert(*plist);
  SLNode* cur = (*plist)->next;
  free(*plist);
  *plist = cur;
}

我们在写一个查找功能的代码

SLNode* SLFind(SLNode* plist, SLNodedataType x);

查找我们可以返回这个节点，这样就能和其他功能一起用，比如修改数据，或者在任意位置插入和删除。

SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
  SLNode* pos = plist;
  while (pos->data == x)
  {
    return pos;
    pos = pos->next;
  }
}

这是只考虑找到的情况下，但是难免有时候会出现找不到的情况，让我们来看一下吧，写一个找不到情况下和找到情况下的代码。‘

SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
  SLNode* pos = plist;
  while (pos != NULL)
  {
    if (pos->data == x)
    {
      return pos;
    }
    pos = pos->next;
  }
  return NULL;
}

然后我们可以写一个函数来判断有没有找到。

SLNode*pos = SLFind(n1, 111);
  if (pos != NULL)
  {
    printf("找到了\n");
  }
  else
  {
    printf("找不到\n");
  }

我们看完整代码。

void test1()
{
  //创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  SListPrint(n1);
  SListPushBcak(&n1, 5);
  SListPushBcak(&n1, 6);
  SListPushBcak(&n1, 7);
  SListPushBcak(&n1, 8);
  SListPrint(n1);
  SListPopBack(&n1);
  SListPopBack(&n1);
  SListPrint(n1);
  SListPushFront(&n1, 111);
  SListPushFront(&n1, 222);
  SListPrint(n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPrint(n1);
  SLNode*pos = SLFind(n1, 111);
  if (pos != NULL)
  {
    printf("找到了\n");
  }
  else
  {
    printf("找不到\n");
  }
}

我们如果要找111发现没有找到，因为头删的时候改掉，其实我们竟然这样写了就可以写一个修改的代码，这里就不演示了。

接下来我们要写的是在任意位置删除和插入节点。

void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{
  assert(plist);
  assert(pos);
  SLNode* newnode = CreateSListNode(x);
  if (pos == *plist)
  {
    SListPushFront(plist, x);
  }
  else
  {
    SLNode* prev = *plist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}

测试代码

void test1()
{
  //创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  SListPrint(n1);
  SListPushBcak(&n1, 5);
  SListPushBcak(&n1, 6);
  SListPushBcak(&n1, 7);
  SListPushBcak(&n1, 8);
  SListPrint(n1);
  SListPopBack(&n1);
  SListPopBack(&n1);
  SListPrint(n1);
  SListPushFront(&n1, 111);
  SListPushFront(&n1, 222);
  SListPrint(n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPrint(n1);
  SLNode*pos = SLFind(n1,3);
  if (pos != NULL)
  {
    printf("找到了\n");
    SListPushInsert(&n1, pos, 10086);
  }
  else
  {
    printf("找不到\n");
  }
  SListPrint(n1);
}

在任意位置删除

void SListPopInsert(SLNode** plist, SLNode* pos)
{
  assert(plist);
  assert(*plist);
  assert(pos);
  if (*plist == pos)
  {
    SListPopFront(plist);
  }
  else
  {
    SLNode* prev = *plist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

其实还有可以在任意位置后删除，这样更快，就不用找那个位置前一个位置了，这里就不展示了，

完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLNodedataType;
typedef struct SList
{
  SLNodedataType data;
  struct SList* next;
}SLNode;
void SListPrint(SLNode* plist);
SLNode* CreateSListNode(SLNodedataType x);
void SListPushBcak(SLNode** plist, SLNodedataType x);
void SListPopBack(SLNode** plist);
void SListPushFront(SLNode** plist, SLNodedataType x);
void SListPopFront(SLNode** plist);
SLNode* SLFind(SLNode* plist, SLNodedataType x);
void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x);
void SListPopInsert(SLNode** plist, SLNode* pos);

#include"SList.h"
void SListPrint(SLNode* plist)
{
  SLNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL");
  printf("\n");
}
SLNode* CreateSListNode(SLNodedataType x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SListPushBcak(SLNode** plist, SLNodedataType x)
{
  SLNode*newnode=CreateSListNode(x);
  assert(plist);
  if (*plist == NULL)
  {
    plist = newnode;
  }
  else
  {
    SLNode* tail = *plist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SListPopBack(SLNode** plist)
{
  assert(plist);
  assert(*plist);
  SLNode* tail = *plist;
  SLNode* prev = NULL;
  while (tail->next != NULL)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
}
//
//void SListPopBack(SLNode** plist)
//{
//  assert(plist);
//  assert(*plist);
//  SLNode* tail = *plist;
//  
//  while (tail->next->next != NULL)
//  {
//    
//    tail = tail->next;
//  }
//  free(tail->next);
//  tail->next = NULL;
//  
//}
void SListPushFront(SLNode** plist, SLNodedataType x)
{
  assert(plist);
  SLNode* newnode = CreateSListNode(x);
  if (*plist == NULL)
  {
    *plist = newnode;
  }
  else
  {
    newnode->next = *plist;
    *plist = newnode;
  }
}
void SListPopFront(SLNode** plist)
{
  assert(plist);
  assert(*plist);
  SLNode* cur = (*plist)->next;
  free(*plist);
  *plist = cur;
}
//SLNode* SLFind(SLNode* plist, SLNodedataType x)
//{
//  SLNode* pos = plist;
//  while (pos->data == x)
//  {
//    return pos;
//    pos = pos->next;
//  }
//}
SLNode* SLFind(SLNode* plist, SLNodedataType x)
{
  SLNode* pos = plist;
  while (pos != NULL)
  {
    if (pos->data == x)
    {
      return pos;
    }
    pos = pos->next;
  }
  return NULL;
}
void SListPushInsert(SLNode** plist, SLNode* pos, SLNodedataType x)
{
  assert(plist);
  assert(pos);
  SLNode* newnode = CreateSListNode(x);
  if (pos == *plist)
  {
    SListPushFront(plist, x);
  }
  else
  {
    SLNode* prev = *plist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}
void SListPopInsert(SLNode** plist, SLNode* pos)
{
  assert(plist);
  assert(*plist);
  assert(pos);
  if (*plist == pos)
  {
    SListPopFront(plist);
  }
  else
  {
    SLNode* prev = *plist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

测试主函数的也发一下吧，大家可以不用放一起测试，有点看不过来。

#include"SList.h"
void test1()
{
  //创建节点
  SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  assert(n1);
  SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  assert(n2);
  SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  assert(n3);
  SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  assert(n4);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  SListPrint(n1);
  SListPushBcak(&n1, 5);
  SListPushBcak(&n1, 6);
  SListPushBcak(&n1, 7);
  SListPushBcak(&n1, 8);
  SListPrint(n1);
  SListPopBack(&n1);
  SListPopBack(&n1);
  SListPrint(n1);
  SListPushFront(&n1, 111);
  SListPushFront(&n1, 222);
  SListPrint(n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPopFront(&n1);
  SListPrint(n1);
  SLNode*pos = SLFind(n1,3);
  if (pos != NULL)
  {
    printf("找到了\n");
    SListPushInsert(&n1, pos, 10086);
  }
  else
  {
    printf("找不到\n");
  }
  SListPrint(n1);
}
int main()
{
  test1();
  return 0;
}

今天的分享就到这里，我们下次再见。

数据结构单链表

热门文章

最新文章

相关课程

相关电子书