数据结构笔记

数据结构笔记(一)

链表:

链表是由一系列成为表的节点(node)的对象构成的。链表是动态的,也就是说,链表能按需求为表中新元素分配空间。

1.1 单向链表:

链表中的每个节点只有一个指向下一个节点的指针,称作单链表或单向表。

链表的第一个元素通过head 指针访问,为了方便对链表尾端节点的访问,通过tail 指针指向链表的最后一个节点,此外还需要一个curr指针指向当前的节点的前一个节点。

为什么curr指针不指向当前节点,而是指向的前一个节点?

如果将curr指向前一个节点,那么就很容易在curr之后插入一个元素了,当我们需要在链表中插入一个节点的时候,
我们首先新建一个节点并且给它赋值,再将新建节点的next域指向当前节点(curr所指节点的下一个节点),再将curr所指的next域指向当前节点:

new Node()->next=curr->next;curr->next=new Node();

如图:

new Node创造了一个新的节点,新节点的next域赋值为curr-next。而curr所指的节点的next域指向到新节点,这样就完成了链表的插入,时间复杂度是Θ(1)。

而从链表中删除一个节点只需要重定向待删除节点周围指针即可:

Node* temp=curr->next curr->next=curr->next->next

删除时需要注意,将待删除指针指向临时指针,调用delete 释放被删除节点占用的内存。删除一个节点的时间复杂度同样是Θ(1)。

1.2 双链表:

双链表可以从一个表节点出发,在线性表中随意访问它的前驱节点和后继节点,它存储了两个指针,一个指向它的前驱节点,另一个一个指向它的后继节点。

和单链表不同的是,双链表额外在链表尾部加入了一个尾节点,不包含任何数据,为了保持概念的一致,本文中curr依旧指向当前节点的前驱节点,与单链表一致。

双链表的插入:

new Node->next=curr->next
curr->next=curr->next->prev=new Node

如图所示:

同理,双链表的删除如下:

1
2
3
4
5
Temp = curr->next->element;
TempLink* ltemp=curr->next;
curr->next->next-prev=curr;
curr->next=curr->next->next;
delete ltemp;

首先对对Temp赋值为将要删除的节点数值,然后将被删节点的后继节点的prev指针指向其前驱节点(curr),接着将其前驱节点的后继节点指向其后继节点,这样就完成了链表的连接。