算法创作|单链表的基本操作

问题描述

单链表是链表的一种，是一种链式存取的数据结构。用一组地址任意的存储单元存放线性表中的数据元素，链表中的数据是以结点（node）来表示的，每个结点的构成包括数据域（date）和指针域（next）两个部分，数据域里存储的是当前结点的数据，指针域能得到该结点的下一结点。

单链表的特点是链表的连接方向是单向的，对链表的访问要通过顺序读取从头部开始。

【图1】

它的优点是可以克服顺序线性表需要预先知道数据大小的缺点，充分利用内存空间，实现灵活的内存动态管理；同时数据元素不需要按顺序存储，还方便进行插入、删除等操作；缺点是查找某个特定结点时速度比顺序存储慢，而且增加了结点的指针域，空间开销较大。

解决方案

例（1）：结点P的赋值操作：

【图2】

则p. data=10    p.next=q

q. data=20   q. next=None

【图1】中，若P=n2，则P和n2等价；若P=P. next，则P就移动到了n3。

即：p=head

p=p. next=n1

p=p. next=n2

……

例（2）：结点P的移动：

若P的初始位置为head，要让P移动到第i个结点，则：

p=head

for k in range (i):

p=p. next

此时P为单链表的第i个结点。

若P的初始位置在head，让P指向单链表的最后一个结点，则：

p=head

while p != None :

p=p. next

print (p.data)

此时P为None。

例（3）：单链表的插入算法：包括尾插法、前插法、任意位置插入法。重点为前两个。

○尾插法：若当前链表尾结点为P，新插入q结点，则 p. next=q , q. next=None。如果让P仍为尾结点，则p=p. next。

○头插法：

若只知头结点head，在头结点和第一个结点之间新插入结点q，则：

q. next=head. next

head.next=q

(先安排q后面的结点，再安排q前面的结点)

例（4）：删除操作：

设P为链表的第i-1个结点，删除第i个结点，则：

p. next=p. next.next

例（5）：合并操作：

设法实现两个单链表的合并操作，则：

p=head1

while p. next !=None :

p=p. next

p. next = head2. next

（链表1的最后一个结点的next为链表2的第一个结点）

结语

本文主要围绕单链表的定义、特点、优缺点、符号表示、以及基本操作（赋值、移动、插入、删除、合并）等问题展开，进行了初步的基础学习。我们发现这些代码易看懂但不易自己写出来，有些眼高手低纸上谈兵，知识掌握不全面且不熟练，希望下次能有所进步。

实习编辑：衡辉

作者：钟妍、杨月涵、欧恒丽