C语言顺序表与链表的知识总结与优缺点分析

1.前言

2.2.2 顺序表push_back函数的实现

2.2.3 顺序表pop_back()函数的实现

2.2.4 顺序表push_front()函数的实现

2.2.5 顺序表pop_front函数的实现

2.2.10 顺序表destroy函数的实现

3.3.1 单链表push_back函数的实现

3.3.2 单链表pop_back函数的实现

3.3.3 单链表push_front的实现

3.3.4 单链表pop_front函数的实现

3.3.9 单链表destroy函数的实现

3.7.1 双向链表push_back函数的实现

3.7.2 双向链表 pop_back函数的实现

3.7.3 双向链表 push_front函数的实现

3.7.4 双向链表 pop_front 函数的实现

3.7.5 双向链表 find函数的实现

3.7.6 双向链表 Insert函数的实现

3.7.7 双向链表 erase函数的实现

3.7.8 双向链表print函数的实现

3.7.9 双向链表 destroy函数的实现

4. 链表与顺序表的优缺点分析

5. 结语

1.前言

数据结构顾名思义是储存数据的结构，学习数据结构之前，一般我们储存数据用到的都是数组，数组的能力很强，可以模拟实现各种数据结构，但是不能根据需要来合理分配空间，一旦数组的长度确定那就无法扩容。

为了尽可能充分利用空间，实现特定需求的数据存储与访问，我们需要一些特别的数据存储方式。顺序表与链表是数据结构的入门结构，本文将用结构体与指针来实现顺序表与链表。

ps：顺序表与链表都属于线性表，线性表还有栈，队列，字符串等

2.顺序表

顺序表与数组类似是一块连续的存储空间，分为静态顺序表与动态顺序表。

这里我们只讲动态顺序表。

2.1创建一个顺序表

顺序表（SeqList）有3个基本属性：

首元素地址（数组名）
有效数据个数
容量空间的大小

定义一个结构体作为顺序表。

typedef struct SeqList
{
    // 指向动态开辟的数组
	DataType* a;
    // 有效数据个数
	size_t size;
    // 容量空间的大小
	size_t capacity;
}SL;

int main()
{
    SL s;
}

因为我们要实现的是动态的顺序表，所以要用到动态内存管理那一块的知识，用malloc与realloc来解决创建与扩容问题。

我们知道：一开始，顺序表的size与capacity都是0，起始地址a也还未知，（此时三个属性都为随机值）因此我们需要先初始化顺序表。

void SeqList_Init(struct SeqList* ps)
{
	ps->a = 0;
	ps->size = 0;
	ps->capacity = 0;
}

2.2 使用顺序表

2.2.1 扩容与倍增

由于刚初始化的顺序表容量为0，我们需要对其进行扩容处理，那么什么时候扩容呢？一次扩容多少合适呢？

如果一次扩容太多会导致空间的浪费，扩容太少，那么扩容的次数也会变多，使得效率低下。这里我们需要了解一下，在申请内存空间时，一次申请10kb与一次申请1kb的时间是一样的，但是一次申请10kb的时间比1kb申请十次的时间要短，

影响时间的最大因素是申请空间的次数

。

所以我们扩容时采用倍增的方式，每一次扩容到原来空间的200%，在有效数据等于容量大小时进行扩容操作。

这里插一个realloc的小知识：当内存中realloc申请的空间过大，那么realloc会移动到一个新地址中，将原空间的内容copy到新地址后完成扩容，叫做异地扩容。

了解完这些后，我们就可以思考如何使用顺序表了，类比一下数组，我们可以将数据一个一个地推进顺序表中，

类似于推箱子，话不多说，我们尝试推入一个元素吧！

2.2.2 顺序表push_back函数的实现

void SeqList_PushBack(struct SeqList* ps, DataType x)
{
    //如果容量=有效数据量，那么我们进行倍增扩容
	if (ps->size == ps->capacity)
	{
        //判断是否为第一次扩容，因为第一次的容量为0，无法倍增
		DataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

        //因为顺序表开辟的空间是连续的，有可能出现扩容失败的情况，所以先用tmp接收
		DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * newcapacity);

        //如果扩容失败，那么tmp为NULL
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

        //如果扩容成功，那么可以将tmp的地址赋给a
		ps->a = tmp;

        //记录下新容量的大小
		ps->capacity = newcapacity;
	}
    //类比一下数组相当于a[size] = x;
	*(ps->a + ps->size) = x;

    //此时size永远指向顺序表最后一个元素的下一位
	ps->size++;
}

在push_back()函数中，其实只有最后两步是push_back的操作，其他部分都是倍增扩容的操作。

这样看来，顺序表是不是很像我们的数组呢？

此外，假如我们想删除最后一个元素，该怎么办呢？

2.2.3 顺序表pop_back()函数的实现

void SeqList_PopBack(struct SeqList* ps)
{
	assert(ps->size > 0);
	if (ps->size > 0)
	{
		ps->size--;
	}
}

ps：assert是C的库函数（assert.h），用于检查。

是的，我们只需要让size减1就可以了，并不用修改原来的数据，因为size决定了我们合法的操作范围，并且往后如果再有数据插入，那么原来的那个数据将会被覆盖。

值得注意的是，假如顺序表是空的，没有一个元素，那么删除操作将是不合法的。

下面要介绍一下并不太适合顺序表的两个操作：前插和前删。

2.2.4 顺序表push_front()函数的实现

如果要在数组第一个元素前插入一个元素，我们该怎么办呢？

其实和尾插一样，我们需要考虑到，新插入一个元素后，顺序表会不会满容量？怎么对空顺序表进行前插？如何调整元素的位置？

void SeqList_PushFront(SL* ps, DataType x)
{
    //检查是否需要扩容
	if (ps->capacity == ps->size)
	{
		DataType newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

    //从最后一个元素开始，每一个元素往后移动一位，直到空出第一位
	for (int i = 0; i < ps->size; i++)
	{
		*(ps->a + ps->size - i) = *(ps->a + ps->size - i - 1);
	}
    //插入数据
	ps->size++;
	*(ps->a) = x;
}

我们能在前面插入一个元素同时也可以在前面删去一个元素，两者的时间复杂度都是O（N）。

如何在前面删去一个元素呢？相信大家应该都有答案了，那就是覆盖。

2.2.5 顺序表pop_front函数的实现

请看注释

void SeqList_PopFront(SL* ps)
{
	assert(ps->size > 0);
    //从第一个元素开始，将后一个元素覆盖前一个元素
	for (int i = 0; i < ps->size - 1; i++)
	{
		*(ps->a + i) = *(ps->a + i + 1);
	}
	ps->size--;
}

是不是很简单呢？

我们把数据存入顺序表，那么当我们需要查找那个数据时就需要用到查找函数。

2.2.6 顺序表find函数的实现

查找函数是为了方便我们查找到合适的数据，同时我们可以进行进一步的操作。

int SeqList_Find(SL* ps, DataType x)
{
    //类比数组，遍历查找就行
	for (int i = 0; i < ps->size; i++)
	{
		if (x == *(ps->a + i))
		{
			printf("此元素在顺序表中的下标是 ");
			return i;
		}
	}
    //找不到就返回-1
	return -1;
}

找到后，如果我们想要删除这个数据，或者想在这个数据前后插入一个数据，那么就会用到erase和insert函数了。

2.2.7 顺序表erase函数的实现

其实原理和pop_front函数一样，都是覆盖。

pos需要用到find函数来找到。

void SeqList_Erase(SL* ps, int pos)
{
	assert(pos <= ps->size && pos >= 0);
	for (int i = 0; i < ps->size - 1 - pos; i++)
	{
		*(ps->a + i + pos) = *(ps->a + i + 1 + pos);
	}
	ps->size--;
}

2.2.8 顺序表Insert函数的实现

同理，Insert函数的原理与push_front类似。

pos用find函数找到，在pos后面插入一个数据。

void SeqList_Insert(SL* ps, int pos, DataType x)
{
	assert(pos >= 0 && pos <= ps->size);
    //同理，需要检查是否需要扩容
	if (ps->capacity == ps->size)
	{
		DataType newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		DataType* tmp = (DataType*)realloc(ps->a, sizeof(DataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

    //在pos位置后插入一个数据。
	for (int i = 0; i < ps->size - pos; i++)
	{
		*(ps->a + ps->size - i) = *(ps->a + ps->size - i - 1);
	}
	ps->size++;
	*(ps->a + pos) = x;
}

2.2.9 顺序表print函数的实现

到这里，我们已经可以对顺序表进行增删查改了，那么如何输出顺序表呢？是的，和数组一样，只要通过下标遍历一遍即可！

void SeqList_Print(struct SeqList* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}

	printf("\n");
	printf("%d\n", ps->size);
	printf("%d\n", ps->capacity);
}

2.2.10 顺序表destroy函数的实现

在使用完顺序表之后，我们需要释放空间，顺序表的销毁也很简单直接释放掉即可，同时，将指针置空。

void SeqList_Destroy(SL* ps)
{
	ps->capacity = 0;
	ps->size = 0;
	free(ps->a);
	ps->a = NULL;
}

到这里，我们已经用C来实现顺序表，并且实现对顺序表的增删查改了。实际应用中，我们通过函数来操作顺序表，实现对数据的储存和管理，需要使用时，通过下标可以直接访问到数据。但是，顺序表的缺点很明显，就是在进行push_front、pop_front和Insert操作时，时间复杂度很高，并且数据量多时需要一大块连续的空间。

3.链表

在实际中，为了实现数据的快速插入与删除，引入了一个叫链表的数据结构。链表像一个链条，分为很多种，本文只介绍单链表与带头双向循环链表。

3.1 单链表

不带头单链表的形状如下图：

带头单链表则如下图：

我们先说不带头的单链表：

不带头的单链表只有两种属性：

需要存储的数据类型
下一个结点的地址

typedef struct SListNode
{
    //你需要存储的数据类型，这里我设置成int
	SLTDataType data;
    //下一个结点的地址
	struct SListNode* next;
}SLTNode;

这样便定义好了结点的基本属性，我们需要用函数来创建每一个新的结点。

3.2 单链表创建新结点

下面的函数会创建一个新的结点，也是后面操作链表时需要用到的基本函数。

SLTNode* BuySListNode(SLTDataType x)
{
    //创建新结点
	SLTNode* plist = (SLTNode*)malloc(sizeof(SLTNode));
    //判断是否创建失败，失败则plist==NULL
	if (plist == NULL)
	{
		perror("create fail");
		exit(-1);
	}

    //为这个结点赋值
	plist->data = x;
	plist->next = NULL;
	
    //返回这个结点的地址
	return plist;
}

像这样，我们就能在堆区创建好一个新的结点，并且得到这个结点的地址。

多说几句，学习链表对指针的知识有一定要求，要谨记拿到谁的地址就能真正修改谁，比如拿到结构体的地址就能修改结构体成员，拿到结构体地址的地址就能修改结构体的地址（plist）。

知道如何创建新结点后，我们就可以思考如何使用单链表了。

3.3 使用单链表

与顺序表一样，我们需要储存数据，就得学会将每一个结点的数据串联起来，将数据存入链表需要用到push_back函数。

3.3.1 单链表push_back函数的实现

首先，我们往链表中推入一个元素时，得先判断推进的是不是链表的第一个元素，如果是，那么我们就要修改头结点的地址，所以我们在进行传参时用的是二级指针（&plist），目的就是为了方便修改头结点的地址。如果不需要修改头节点，二级指针也依然能够完成他的使命。

void SListPushBack(SLTNode** pplist, SLTDataType x)
{
    //创建新结点
	SLTNode* newnode = BuySListNode(x);

    //从链表的头结点开始，定义一个tail指针来找到最后链表的最后一个结点
	SLTNode* tail = *pplist;
   
    //如果tail == NULL 那则说明该结点是第一个推进链表的结点，需要设置成头结点
	if (tail == NULL)
	{
        //将头结点的地址修改成这个新创建的结点的地址
		*pplist = newnode;
	}
	else
	{
        //如果新结点不是链表的第一个结点，那么tail将循环找到最后一个结点
		while (tail->next)
		{
			tail = tail->next;
		}

        //找到最后一个结点后，将最后一个结点的成员next指向新的结点，实现结点之间的串联
		tail->next = newnode;
	}
}

通常在主函数中，我们需要自己创建一个结构体指针，然后进行操作。

int main()
{
	SLTNode* plist = NULL;
    SListPushBack(&plist, 20);
	return 0;
}

我们有尾插函数，同样的也有尾删函数，和顺序表一样，删除之前要检查一遍，不能对空链表进行删除操作。

3.3.2 单链表pop_back函数的实现

尾删包括两个步骤：

找到尾结点
删除

void SListPopBack(SLTNode** pplist)
{
    //判断是否为空链表
	assert(*pplist);

    //prev记录需要删掉的那个结点的前一个结点，目的是把该结点的next=NULL
	SLTNode* prev = *pplist;
    //tail记录需要删除的，也就是尾结点
	SLTNode* tail = *pplist;

	while (tail->next)
	{
		prev = tail;
        //tail走到下一个结点
		tail = tail->next;
	}

    //释放尾结点的空间
	free(tail);
	prev->next = NULL;

}

因为有可能会删除头结点，此时我们需要用到二级指针。尾插可能还不是很能体现链表的优点，下面我们进行头插来观察一下。

3.3.3 单链表push_front的实现

因为头插要改变头节点，所以我们需要用到二级指针。

void SListPushFront(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

    //让新结点的next指向头结点
	newnode->next = *pplist;
    //将头结点的地址改为新结点的地址
	*pplist = newnode;
}

可以看到，此时的时间复杂是是O（1），而顺序表的时间复杂度是O（n）。可以看出链表插入数据的优点。同样还有头删。

3.3.4 单链表pop_front函数的实现

头删需要注意链表不能为空，操作前需要检查链表，需要改变头结点，所以需要用到二级指针。

void SListPopFront(SLTNode** pplist)
{
	assert(*pplist);

    //存下头结点的下一个结点的地址
	SLTNode* next = (*pplist)->next;
    //释放头结点
	free(*pplist);
    //头结点的地址指向下一个结点
	*pplist = next;
}

头删的时间复杂度也仅为O（1）。

3.3.5 单链表find函数的实现

单链表的一个特点是只能由前一个找到后一个，所以和顺序表一样，直接遍历就可以了。

SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* tail = plist;
	if (plist == NULL)
	{
		return NULL;
	}
	else if(tail->data == x)
	{
		return tail;
	}
	else
	{
		tail = tail->next;
		SListFind(tail, x);
	}
}

这里用了递归，但是循环也能实现，所以其实无所谓，能找到就可以了。

3.3.6 单链表Insert函数的实现

在单链表中，插入操作也很方便。

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
    //先连接好新结点的next，再改原结点的next
	newnode->next = pos->next;
	pos->next = newnode;
}

时间复杂度是O（1）。

3.3.7 单链表erase函数的实现

删除主要是删除某结点后的一个结点，因为只能由前一个结点找到后一个结点，所以是删除后一个。

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}

    //记录下需要删除的结点（pos->next）的下一个结点
	SLTNode* next = pos->next->next;

    //删除pos->next的结点
	free(pos->next);

    //将pos->next指向next结点
	pos->next = next;
}

其实无论是删除操作，都需要在前面检查一遍是否为空。时间复杂度为O(1)。

3.3.8 单链表print函数的实现

从头结点开始，遍历到最后一个结点即可。

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

3.3.9 单链表destroy函数的实现

使用完链表后，需要及时释放空间，销毁链表。

void SListDestroy(SLTNode** plist)
{
	if ((*plist)->next == NULL)
	{
		return;
	}
	SListDestroy(&(*plist)->next);
	free(*plist);
	*plist = NULL;
}

这里也是用了递归的方式，但是建议大家用循环来解决，毕竟递归是有缺点的。

到这里，我们已经实现了对单链表的增删查改，但是链表有很多种，单链表只是其中一种比较常见的，还有另外两种在下文会有介绍。

3.4 带头单链表

带头单链表的操作其实与单链表非常类似。

但是为了结构的统一，我会把头指针也创建为一个结点，但是头结点的数据我不会去使用，仅仅作为一个头领的作用。有什么用呢？就是方便头插，头插的时候不用改变头结点，因此不用二级指针也可以完成头插和头删。头结点（plist）的next就是链表中储存的第一个数据。

3.5 带头双向循环链表

这种链表的结构开始复杂了一些，由于结构的复杂，使用也方便了许多。

来看一下该链表的结构。

这里的头结点会一直在最左边，只对头结点的右侧进行增删查改。这个链表有不少优势：

可以访问上一个结点
可以轻松找到尾结点
可以忽略很多检查步骤

接下来让我们看看结点的结构

typedef int LTDataType;

typedef struct ListNode
{
    //数据类型
	LTDataType data;
    //下一个结点的位置
	struct ListNode* next;
    //上一个结点的位置
	struct ListNode* prev;
}ListNode;

知道了结点的结构，那么我们现在就来创建一个头结点吧！

3.6 带头双向循环链表创建新结点

// 创建返回链表的头结点.
ListNode* ListCreate()
{
    //创建
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
    
    //判空
	ListNode* phead = NULL;
	if (tmp == NULL)
	{
		exit(-1);
		perror("create fail");
	}
	else
	{
		phead = tmp;
	}

    //初始化
	phead->data = 0;
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

主函数里创建新结点。

int main()
{
    //创建头结点
	ListNode* phead = ListCreate();

	ListPushBack(phead, 5);
	ListPushBack(phead, 6);

	ListPushFront(phead, 11);

	ListPopFront(phead);
	ListPopFront(phead);

	ListInsert(ListFind(phead, 6), 5);

	ListErase(ListFind(phead, 6));

	ListPrint(phead);

	ListDestory(phead);

	return 0;
}

ps：头结点的data其实是没有用处的。

每个结点创建的时候让prev和next指向自己，这样能形成一个小循环，方便第二个结点的插入。

这个链表没有指向NULL的指针。

3.7 使用双向链表

先来说说双链表是如何存结点的吧。

3.7.1 双向链表push_back函数的实现


// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
    //先要判断是否有头结点
	assert(pHead);

    //头结点的前一个就是尾结点，因为是循环的
	ListNode* ptail = pHead->prev;

    //创建新结点
	ListNode* newnode = ListCreate();

    //赋值
	newnode->data = x;

    //连接
	newnode->next = pHead;
	newnode->prev = ptail;
	pHead->prev = newnode;
	ptail->next = newnode;
}

连接prev和next的时候，可以按习惯来。

接下来要就是弹出尾结点的操作。

3.7.2 双向链表 pop_back函数的实现

其实和单链表的操作类似

断开
释放
连接

三步走即可

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
    //若只存在头结点，那么不可以删除
    assert(pHead->next!=pHead);

    //头结点的prev指针指向尾结点
	ListNode* ptail = pHead->prev;
	ListNode* prev = ptail->prev;

	free(ptail);
	ptail = NULL;

	prev->next = pHead;
	pHead->prev = prev;
}

3.7.3 双向链表 push_front函数的实现

要点和之前的差不多，搞清楚连接的逻辑即可。

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
    assert(pHead);
	ListNode* newnode = ListCreate();
	ListNode* nextnode = pHead->next;

	newnode->data = x;

	newnode->next = nextnode;
	newnode->prev = pHead;

	nextnode->prev = newnode;
	pHead->next = newnode;
}

3.7.4 双向链表 pop_front 函数的实现

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead->next != pHead);

	ListNode* delenode = pHead->next;
	ListNode* nextnode = delenode->next;

	free(delenode);
	delenode = NULL;

	pHead->next = nextnode;
	nextnode->prev = pHead;
}

3.7.5 双向链表 find函数的实现

查找和单链表查找思路一致。

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("查找失败，不存在该结点");
	return NULL;
}

这里用的是循环的思路。

3.7.6 双向链表 Insert函数的实现

一般Insert函数的使用都是和find搭配的，当find函数找不到结点时，pos为NULL，需要检查，另外

pos不可以是头结点

。

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);

	ListNode* newnode = ListCreate();
	ListNode* prevnode = pos->prev;
	
	newnode->data = x;

	newnode->next = pos;
	newnode->prev = prevnode;

	prevnode->next = newnode;
	pos->prev = newnode;
}

3.7.7 双向链表 erase函数的实现

注意，

pos不能是头结点

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prevnode = pos->prev;
	ListNode* nextnode = pos->next;

	free(pos);
	pos = NULL;

	prevnode->next = nextnode;
	nextnode->prev = prevnode;
}

3.7.8 双向链表print函数的实现

与单链表一模一样。

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("pHead");
}

3.7.9 双向链表 destroy函数的实现

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->prev;
	ListNode* prev = pHead;
	while (cur != pHead)
	{
		prev = cur->prev;
		free(cur);
		cur = NULL;
		cur = prev;
	}
	pHead->next = pHead;
	pHead->prev = pHead;
}

用循环的方式free每一个结点，但是头结点无法删除，因为我们只用到了一级指针。

这就是带头双向链表的增删查改了，双向链表的结构比较复杂，但是带来了许多操作上的遍历，减少了很多运算。

4. 链表与顺序表的优缺点分析

顺序表最容易让人想到的优点在于

支持下标访问
内存空间是连续的
对缓存的利用率高

在需要高效存储和频繁访问的情境下优先考虑顺序表。

顺序表的缺点也很明显

需要扩容
插入和删除的时间复杂度高

而链表则可以解决顺序表的劣势问题，链表的优点在于

插入删除的时间复杂度底
不需要扩容

但其劣势也很明显

不支持随机访问
缓存利用率低

在需要频繁删除和插入数据的情况下有限考虑链表。

所以说各有长处。得需要根据情况而定。

5. 结语

顺序表与链表属于简单的数据结构，链表更是后续复杂结构的基石。

同时顺序表和链表涉及多种算法，最经典的莫过于快慢指针。需要多加练习。

用C实现两种结构可以清楚其原理，后续会更新更多用C语言实现的数据结构知识。

原文链接：https://blog.csdn.net/GMfengyi/article/details/128367473

1.前言

2.顺序表

2.1创建一个顺序表

2.2 使用顺序表

2.2.1 扩容与倍增

2.2.2 顺序表push_back函数的实现

2.2.3 顺序表pop_back()函数的实现

2.2.4 顺序表push_front()函数的实现

2.2.5 顺序表pop_front函数的实现

2.2.6 顺序表find函数的实现

2.2.7 顺序表erase函数的实现

2.2.8 顺序表Insert函数的实现

2.2.9 顺序表print函数的实现

2.2.10 顺序表destroy函数的实现

3.链表

3.1 单链表

3.2 单链表 创建新结点

3.3 使用单链表

3.3.1 单链表push_back函数的实现

3.3.2 单链表pop_back函数的实现

3.3.3 单链表push_front的实现

3.3.4 单链表pop_front函数的实现

3.3.5 单链表find函数的实现

3.3.6 单链表Insert函数的实现

3.3.7 单链表erase函数的实现

3.3.8 单链表print函数的实现

3.3.9 单链表destroy函数的实现

3.4 带头单链表

3.5 带头双向循环链表

3.6 带头双向循环链表 创建新结点

3.7 使用双向链表

3.7.1 双向链表push_back函数的实现

3.7.2 双向链表 pop_back函数的实现

3.7.3 双向链表 push_front函数的实现

3.7.4 双向链表 pop_front 函数的实现

3.7.5 双向链表 find函数的实现

3.7.6 双向链表 Insert函数的实现

3.7.7 双向链表 erase函数的实现

3.7.8 双向链表print函数的实现

3.7.9 双向链表 destroy函数的实现

4. 链表与顺序表的优缺点分析

5. 结语

你可能也喜欢

3.2 单链表创建新结点

3.6 带头双向循环链表创建新结点