黑马程序员技术交流社区

标题: 【上海校区】链表 [打印本页]

作者: 不二晨 时间: 2019-3-15 16:33
标题: 【上海校区】链表
一、链表

数组提供集中的表示法，用一块连续的内存为元素提供存储和引用；
链表提供分布式的表示法，使用被称为节点的轻量级对象，来维护链表中的每个元素和序列顺序。

节点：每个节点维护一个指向它的元素的引用，维护一个或多个指向相邻节点的引用
二、单链表

1、单链表的节点

单链表节点维护两个引用

元素成员：引用一个序列中的一个元素对象
指针域成员：指向该节点的后继节点
头节点（head）和尾节点（tail）标识序列中第一个节点和最后一个节点

当序列不为空时，从头节点开始，通过每个节点的next引用，即可从这个节点移动到下一个节点，从未到达序列的尾节点（当节点的next引用为空时，这个节点即为尾节点）。此过程叫“遍历”链表或“链接跳跃”、“指针跳跃”。
当序列为空时，头节点只是一个形式，头节点的元素和指针域都指向None，此时头节点即尾节点。

2、单链表的结构

链表在内存中的表示依赖许多对象的协作，至少需要维护以下2个对象

一个代表整个链表的对象：一个指向链表头节点的引用
链表中的每个节点对象
尾节点的引用不是必须的：因为可以通过遍历链表来定位尾节点。但有时为了避免为访问尾节点而遍历链表，也会显式地维护一个指向尾节点的引用。
节点总数也不是必须的：同样，避免为了计算链表中的节点数而遍历整个链表，有时链表实例也会维护一个表示节点总数的实例变量。

3、单链表的插入和删除

在头节点处进行插入/删除是简单的
在尾节点（或其他中间节点）插入/删除是复杂的，因为不能直接定位到，需要进行遍历

在单链表L头部插入一个元素
''' 伪代码 '''
add_first(L,e): #L是一个单链表，e是需要插入的元素
newest = Node(e) #通过Node将元素e封装成一个节点
newest.next = L.head
L.head =  newest
L.size += 1
1
2
3
4
5
6
在单链表L头部删除一个元素
''' 伪代码 '''
remove_first(L):
if L.head = None:
raise EmptyError  #头节点为空时，链表为空，无法删除
L.head = L.head.next #链表中至少有1个节点。只有1个节点时，L.head.next为None，删除该节点后，链表头节点指向None，链表为空
L.size -= 1
1
2
3
4
5
6
在单链表尾部插入一个元素
''' 伪代码 —— 当链表维护了一个尾节点对象时'''
add_last(L,e): #L是一个单链表，e是需要插入的元素
newest = Node(e)
newest.next = None
L.tail.next = newest
L.tail = newest
L.size += 1
1
2
3
4
5
6
7
''' 伪代码 —— 当链表没有维护尾节点对象时'''
add_last(L,e): #L是一个单链表，e是需要插入的元素
newest = Node(e)
newest.next = None
tail = L.head
while tail.next != None
tail = tail.next
tail.next = newest
1
2
3
4
5
6
7
8
在单链表尾部删除一个元素
不管我们是否维护了单链表的尾节点对象，都不能轻易地删除单链表的尾节点。
因为删除操作需要定位到尾节点的前驱节点，此操作需要遍历链表（是否维护了尾节点区别不大），此操作需要花费很长的时间。
如果希望有效地实现此操作，一般通过双链表实现
4、单链表的变种——循环链表

循环链表
将链表的尾节点的next指针指向链表的头部，即获得了一个循环链表的结构。
与标准链表相比，循环链表为循环数据集提供了一个更通用的模型，即标准链表的开始和结束没有任何特定的概念。
循环链表的结构
维护一个指向当前节点的引用current
通过设置current=current.next，可以有效地遍历链表
三、双链表

1、双向链表的节点

双链表节点维护两个引用

元素成员：引用一个序列中的一个元素对象
指针域成员：指向该节点的前驱节点（prev）和后继节点（next）
2、双链表的结构

一般维护以下4个对象

一个代表整个链表的对象：一个指向链表头节点的引用
链表中的每个节点对象
头节点和尾节点
有时会设置头哨兵和尾哨兵，这两个节点中并不存储序列中的元素。虽然不设置哨兵节点也能可以实现双向链表，但哨兵只需要占用很小的额外空间就能极大地简化操作逻辑。
节点总数
3、双链表的插入和删除

由于各节点维护了其前驱和后继节点，在双链表头、尾部删除插入节点都比较简单

在双链表D头部插入一个元素
''' 伪代码 '''
add_first(D,e): #D是一个双链表，e是需要插入的元素
newest = Node(e) #通过Node将元素e封装成一个节点
newest.prev = D.header #新节点的前驱节点指向头哨兵
newest.next = D.header.next #新节点的后继节点指向头哨兵的下一个节点（序列中的第一个节点）
D.header.next.prev = newest #原序列中的第一个节点的前驱节点指向新节点
D.header.next =  newest #头哨兵的后继节点指向新节点
L.size += 1
1
2
3
4
5
6
7
8
在双链表D头部删除一个元素
''' 伪代码 '''
remove_first(L):
old = L.header.next    #原序列中的第一个节点
old.next.prev = L.header #原序列中的第二个节点的前驱节点指向头哨兵
L.header.next = old.next #头哨兵的后继节点指向原序列中的第二个节点
old = None  #原序列中的第一个节点指向None
L.size -= 1
1
2
3
4
5
6
7
在双链表尾部插入/删除一个元素
基本思想同上，新节点的后继节点指向尾哨兵，新节点的前驱节点指向尾哨兵的前驱节点。
尾哨兵前驱节点的后继节点指向新节点，尾哨兵的前驱节点指向新节点。
伪代码部分不赘述~
---------------------
【转载，仅作分享，侵删】
作者：琪仔要转行回coder
来源：CSDN
原文：https://blog.csdn.net/lllllaaa77/article/details/88412943
版权声明：本文为博主原创文章，转载请附上博文链接！

作者: 不二晨 时间: 2019-3-20 16:55

奈斯，感谢分享

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2