[数据结构]——单链表超详细总结

简介: [数据结构]——单链表超详细总结

目录:

链表是个优秀的结构,没有容量概念,可以在任意位置增加删除数据,这个博客,我准备花大量篇幅去总结链表(特别是单链表),同时也总结一下顺序表(顺序表和我们以前写的通讯录动态版类似,一般采用数组存储的方法,在数组上完成数据的增删查改)


一、线性表的概念

线性表的定义:由n个数据元素组成具有相同特性的有限序列。

常见的线性表:顺序表、链表、栈、队列、字符串等等。

线性表的概念:线性表在逻辑上是线性结构,也就是说它是一条直线,它的物理结构并不一定是连续的,线性表在物理上存储时,通常以数组和链表的形式存储。


二、顺序表

顺序表的定义:

顺序表是一段物理地址连续的存储单元,是一种用来依次存储数据的线性结构


1.静态顺序表:使用定常数组存储元素

#define N 7//方便改变数组大小
typedef int SLDatatype;
typedef struct SLD
{
SLDatatype arr[N];//定长数组
size_t size;//有效数据的个数
}SeqList;//顺序表

2.动态顺序表:使用动态开辟的数组存储元素(空间不够就可以扩容)

typedef int SLDatatype;
typedef struct SLD
{
SLDatatype* p;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capicity;//表示容量空间的大小
}SeqList;//顺序表

三、链表

3.1 链表的概念

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

注意:

链式结构在逻辑上是连续的,但是在物理上不一定连续。

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

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


3.2 链表的分类

链表的结构非常多,结合起来有8种:

1、单向或者双向


2、带头或者不带头

3、循环或者不循环

实际中常用的两种结构是:


无头单向非循环链表 :

结构简单,一般不会单独存数据。其他数据的子结构,如哈希桶、图的领接表等等。

带头双向循环链表:

结构最复杂,一般可以单独存数据。实际中使用的链表数据结构,都是带头双向循环链表。

3.3 无头+单向+非循环链表的实现

头文件里的函数声明

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);

下面将是各个函数的实现

// slist.c
#include "SList.h"
//动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
//在堆上开辟一个存放指针的变量,并给它初始化
  SListNode* node = (SListNode*)malloc(sizeof(SListNode));
  node->data = x;
  node->next = NULL;
  return node;//返回指针
}
//单链表打印
void SListPrint(SListNode* plist)
{
//定义一个指针,指针指向头指针
  SListNode* cur = plist;
  //遍历指针,不是空就循环
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  //cur指向空
  printf("NULL\n");
}
//单链表尾插一个数据
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//开辟一个新结点
  SListNode* newnode = BuySListNode(x);
  //如果头指针指向的是空就让它指向这个新结点
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else//如果头指针指向的不是空
  {
  //创建一个尾指针
    SListNode* tail = *pplist;
    //尾指针不在尾部,遍历单链表,让尾指针指向链表的最后结点
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
//把开辟的新结点尾插到尾指针结点的下一个结点
    tail->next = newnode;
  }
}
//单链表尾删
void SListPopBack(SListNode** pplist)
{
//定义两个指针
  SListNode* prev = NULL;//当前位置的指针
  SListNode* tail = *pplist;//尾结点的指针
  // 1.空、只有一个节点
  // 2.两个及以上的节点
  if (tail == NULL || tail->next == NULL)
  {
//给空间释放
    free(tail);
    *pplist = NULL;
  }
  else
  {
  //遍历链表,找到尾指针
    while (tail->next)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail = NULL;
//让最后一个结点指向空
    prev->next = NULL;
  }
}
//单链表头插法
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//这个指针是空就报错
  assert(pplist);
  // 1.空
  // 2.非空
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)//pplist指针指向的是空
  {
    *pplist = newnode;
  }
  else
  {
  //在*pplist指针指向的那个结点前面头插一个结点
    newnode->next = *pplist;
    //*pplist指针重新指向头结点
    *pplist = newnode;
  }
}
//单链表头删
void SListPopFront(SListNode** pplist)
{
  // 1.空
  // 2.一个
  // 3.两个及以上
  SListNode* first = *pplist;//定义一个头指针,它为空就返回,
  if (first == NULL)
  {
    return;
  }
  else if (first->next == NULL)//只有一个结点,就释放空间,然后置空
  {
    free(first);
    *pplist = NULL;
  }
  else
  {
  //两个以上结点
    SListNode* next = first->next;//把头指针的下一个结点位置存起来
    free(first);//释放头指针
    *pplist = next;//让首指针重新指向头指针
  }
}
 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
  SListNode* cur = plist;
  while (cur)
  {
    if (cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)//用单链表查找,找到值x的位置,返回的指针给pos
{
  assert(pos);
  SListNode* next = pos->next;//next指针存放pos之后的节点
  SListNode* newnode = BuySListNode(x);//开辟一个新结点
  pos->next = newnode;//在pos后面插入新开辟的结点
  newnode->next = next;//让新结点连接上next指向的那个结点
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)//用单链表查找,找到值x的位置,返回的指针给pos
{
  assert(pos);
  // pos next nextnext
  SListNode* next = pos->next;
  if (next != NULL)
  {
    SListNode* nextnext = next->next;
    free(next);
    pos->next = nextnext;
  }
}
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
    SListNode* cur = *pplist;
    while (cur)
    {
        *pplist = cur->next;
        free(cur);
        cur = *pplist;
    }
}

3.4 带头+双向+循环链表的实现

头文件里的函数声明

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* next;
  struct ListNode* prev;
}ListNode;
//创建新结点
 ListNode* ListNodes(LTDataType x);
//双向链表初始化
 ListNode* ListInit();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
//求链表有多少数据
int listsize(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

函数的定义实现

// 创建新节点
ListNode* ListNodes(LTDataType x)
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    head->data = x;
    head->next = NULL;
    head->prev = NULL;
    return head;
}
//链表初始化
ListNode* ListInit()
{
    ListNode* phead = ListNodes(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = ListNodes(x);//创建一个新节点
    ListNode* tail = phead->prev;
    newnode->data = x;
    //双向链表尾插
    tail->next = newnode;
    newnode->next = phead;
    newnode->prev = tail;
    phead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* tail = phead->prev;
    ListNode* tailPrev = tail->prev;
    free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
    ListNode* next = phead->next;
    ListNode* newnode = ListNodes(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* node = phead->next;
    phead->next = node->next;
    node->next->prev = phead;
    free(node);
}
//求链表有多少数据
int listsize(ListNode* phead)
{
    int  size = 0;
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    ListNode* newnode = ListNodes(x);
    ListNode* prevnode = pos->prev;
    prevnode->next = newnode;
    newnode->prev = prevnode;
    newnode->next = pos;
    pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* nodeprev = pos->prev;
    ListNode* nodenext = pos->next;
    free(pos);
    nodeprev->next = nodenext;
    nodenext->prev = nodeprev;
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{
    //断言指针指针不为NULL
    assert(phead);
    ListNode* cur = phead;//定义一个指针
    //断开循环链表
    phead->prev->next = NULL;
    while (cur)
    {
        ListNode* Next = cur->next;
        free(cur);
        cur = Next;
    }
}

四、顺序表和链表的区别和联系

补充: 高速缓存利用率

先要对存储器的层次结构有一定了解

如图:

数据是存在内存中的,CPU要访问数据,它不会去内存直接访问数据。看数据在不在缓存,在缓存,数据就命中(cpu访问数据时,数据恰好在缓存里),不在缓存,访问不命中(cpu访问数据,不会把4个字节加载到缓存,它会把一长段的数据加载到缓存)


注意:CPU访问数据第一次不命中,第二次一定命中


相关文章
|
3月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
28天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
22天前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
22 1
|
2月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
1月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
1月前
|
存储
数据结构2——单链表
数据结构2——单链表
31 1
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
22天前
|
存储
数据结构(单链表)
数据结构(单链表)
9 0
|
1月前
|
存储
数据结构--单链表
数据结构--单链表
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)