个人中心
退出
数据结构与算法-链表
数据结构与算法-链表
01
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；
02
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成；
03
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂；
04
由于不必须按顺序存储，链表在插入的时候以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)；
05
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大；
06
链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换；
07
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表、双向链表以及循环链表。
（1）单向链表：单链表是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。
（2）双向链表：双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
（3）循环链表：循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。
链表的特点
01
链表是一种非线性、非顺序的物理结构，是由若干个节点组成；
02
链表采用的是“见缝插针”的存储方法，不要求内存连续，靠next指针关联起来；
03
链表的物理存储方式为随机存储，访问方式为顺序访问；
04
查找节点的时间复杂度为O(n)，插入、删除节点的时间复杂度为O(1)；
05
链表适用于写操作多，读操作少的场景。
Python实现单链表
01
单链表是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。
单链表节点的链接方向是单向的；相对于数组来说，单链表的的随机访问速度较慢，但是单链表删除/添加数据的效率很高。
# 链式 内存不连续，无法通过下标直接进行访问，追加元素比较方便，find比较麻烦，需要重头到尾进行遍历
# 单链 root节点，head节点，tail节点，每一个节点就是一个Node(value,next)
class Node(object):
def __init__(self, value=None, next=None):
self.value, self.next = value, next
class LinkedList(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
self.root = Node()
self.length = 0
self.tail_node = None
def __len__(self):
return self.length
def append(self, value):
if self.maxsize is not None and len(self) > self.maxsize:
raise Exception('The list is full')
node = Node(value)
tail_node = self.tail_node
if tail_node is None:
self.root.next = node
else:
tail_node.next = node
self.tail_node = node
self.length += 1
def append_left(self, value):
headnode = self.root.next
node = Node(value)
self.root.next = node
node.next = headnode
self.length += 1
def iter_node(self):
current_node = self.root.next
while current_node is not self.tail_node:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
def remove(self, value):
previous_node = self.root
current_node = self.root.next
for current_node.value in self.iter_node():
if current_node.value == value:
previous_node.next = current_node.next
if current_node is self.tail_node:
self.tail_node = previous_node
del current_node
self.length -= 1
return 1
else:
previous_node = current_node
return -1
def find(self, value):
index = 0
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1
def pop_left(self):
if self.root.next is None:
raise Exception('pop from empty linked list')
head_node = self.root.next
self.root.next = head_node.next
self.length -= 1
value = head_node.value
del head_node
return value
def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.length = 0
Python实现双向链表
02
双向链表(双链表)是链表的一种，和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
class Node(object):
__slots__ = ('value', 'prev', 'next') # save memory
def __init__(self, value=None, prev=None, next=None):
self.value, self.prev, self.next = value, prev, next
class CircularDoubleLinkedList(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.next, node.prev = node, node
self.root = node
self.length = 0
def __len__(self):
return self.length
def headnode(self):
return self.root.next
def tail_node(self):
return self.root.prev
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value=value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception('LinkedList is Full')
node = Node(value=value)
if self.root.next is self.root: # empty
node.next = self.root
node.prev = self.root
self.root.next = node
self.root.prev = node
else:
node.prev = self.root
headnode = self.root.next
node.next = headnode
headnode.prev = node
self.root.next = node
self.length += 1
def remove(self, node):
if node is self.root:
return
else:
node.prev.next = node.next
node.next.prev = node.prev
self.length -= 1
return node
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
def iter_node_reverse(self):
"""相比单链表独有的反序遍历"""
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
作者：David
欢迎关注微信公众号 ：测开笔记
分类导航