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

一、前言之链表的引入

顺序表的问题及思考 ：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容

到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

基于以上的问题，我们可以考虑使用链表的结构来看看。

二、链表的概念及分类

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

中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

组成：每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

注：1、链式结构在逻辑上是连续的，但是在物理上不一定连续。

2、结点一般都是从堆上申请出来的（因为我们要自己开辟空间）。

3、从堆上申请的空间中，两次申请的空间可能连续，也可能不连续。

链表的分类：

而我们在实际应用中最主要使用的是下面两种结构：

三、无头单向非循环链表的实现

首先我们先要定义一个单向链表

typedef int DataType;
typedef struct SListNode
{
  DataType data; //数据域
  struct SListNode* next; //指针域
}SL;

接下来我们实现它的一下相关接口函数：

1、创建一个新的结点

//创建一个新的节点
SL* CreatNewNode(DataType x)
{
  SL* newnode = (SL*)malloc(sizeof(SL));
  if (newnode == NULL)
  {
    printf("malloc fail");
    exit(-1);
  }
  else
  {
    newnode->next = NULL;
    newnode->data = x;
  }
  return newnode;
}

2、头插

//头插
void SLPushFront(SL** pphead, DataType x)
{
  assert(pphead);
  SL* newnode = CreatNewNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

3、头删

//头删
void SLPopFront(SL** pphead)
{
  assert(pphead);
  assert(*pphead);
  SL* cur = (*pphead)->next;
  free(*pphead);
  *pphead = cur;
}

4、尾插

//尾插
void SLPushBack(SL** pphead, DataType x)
{
  assert(*pphead);
  SL* newnode = CreatNewNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  //找尾
  else
  {
    SL* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

5、尾删

//尾删
void SLPopBack(SL** pphead)
{
  assert(pphead);
  assert(*pphead != NULL);
  SL* tail = *pphead;
  SL* prev = NULL;
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {//找尾和前一个
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
    tail = NULL;
  }
}

6、链表的销毁

//销毁
void SLDestroy(SL** pphead)
{
  assert(pphead);
  SL* cur = *pphead;
  while (cur)
  {
    SL* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

7、打印函数

//打印
void print(SL* phead)
{
  SL* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL");
}

8、查找

//查找
SL* SListFind(SL* pphead, DataType x)
{
  assert(pphead);
  SL* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

9、在任意位置之前插入

//在pos之前插入，需要找前一个
void SListInsert(SL** pphead, SL* pos, DataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SL* newnode = CreatNewNode(x);
    SL* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
      assert(prev);
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}

测试一下我们的单向链表：

void SListTest()
{
  SL* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  print(plist);
  printf("\n");
  SLPopFront(&plist);
  print(plist);
  printf("\n");
  SLPushBack(&plist, 33);
  SLPushBack(&plist, 22);
  print(plist);
  printf("\n");
  SLPopBack(&plist);
  print(plist);
  printf("\n");
}
int main()
{
  SListTest();
  return 0;
}

运行结果：

四、带头双向循环链表的实现

首先我们先要定义一个双向链表

typedef int DLdataType;
typedef struct DListNode
{
  DLdataType data;
  struct DListNode* next;//后一个
  struct DListNode* prev;//前一个
}DL;

接下来我们实现它的一下相关接口函数：

1、初始化

//初始化
DL* ListInit()
{
  DL* phead = (DL*)malloc(sizeof(DL));
  if (phead == NULL)
  {
    printf("malloc is fail");
    exit(-1);
  }
  phead->next = phead;
  phead->prev = phead;
    return phead;
}

2、打印函数

//打印
void print(DL* phead)
{
  assert(phead);
  DL* cur = phead->next;
  while (cur != phead)
  {
    printf("%d ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}

3、创建一个新的结点

//创建一个新的节点
DL* CreatNode(DLdataType X)
{
  DL* newnode = (DL*)malloc(sizeof(DL));
  if (newnode == NULL)
  {
    printf("malloc is fail");
    exit(-1);
  }
  newnode->data = X;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}

4、尾插

//尾插
void DLPushBack(DL* phead, DLdataType X)
{
  assert(phead);
  DL* newnode = CreatNode(X);
  DL* tail = phead->prev;
  phead->prev = newnode;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
}

5、头插

//头插
void DLPushFront(DL* phead, DLdataType X)
{
  assert(phead);
  DL* newnode = CreatNode(X);
  if (phead->next == NULL)
  {
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = phead->prev;
  }
  else
  {
    DL* cur = phead->next;
    newnode->prev = phead;
    newnode->next = cur;
    phead->next = newnode;
    cur->prev = newnode;
  }
}

6、头删

//头删
void DLPopFront(DL* phead)
{
  assert(phead);
  DL* cur = phead->next;
  DL* idx = cur->next;
  phead->next = idx;
  idx->prev = phead;
  free(cur);
  cur = NULL;
}

7、尾删

//尾删
void DLPopBack(DL* phead)
{
  assert(phead);
  DL* tail = phead->prev;
  DL* tailprev = tail->prev;
  free(tail);
  tailprev->next = phead;
  phead->prev = tailprev;
}

8、在pos位置之前插入x

void ListInsert(DL* pos, DLdataType x)
{
    assert(pos);
    DL* prev = pos->prev;
    DL* newnode = CreatNode(x);
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

9、链表的销毁

void DLDestory(DL* phead)
{
  assert(phead);
  DL* cur = phead->next;
  while (cur != phead)
  {
    DL* next = cur->next;
    free(cur);
    cur = next;
  }
  free(phead);
}

下面测试一下我们的双向链表：

void TestList1()
{
  DL* plist = ListInit();
  DLPushBack(plist, 1);
  DLPushBack(plist, 2);
  DLPushBack(plist, 3);
  DLPushBack(plist, 4);
  print(plist);
  DLPushFront(plist, 317);
  print(plist);
  DLPopFront(plist);
  print(plist);
  DLPopBack(plist);
  print(plist);
}
int main()
{
  TestList1();
  return 0;
}