链表

一. 链表的基本概念

链表与顺序表 顺序表： 顺序表的构建需要预先知道数据的大小来申请连续的存储空间。而在进行扩充的时候又需要进行数据的搬迁，所以使用起来并不是很灵活。 链表： 是一种线性表，是在每一个节点（数据存储单元）里面粗播放下一个节点的位置（即地址）。链表可以充分利用计算机的内存空间，实现灵活的内存动态管理 顺序表和链表存储的对比：

顺序表和链表插入删除方面时间复杂度：

二. 单链表

概念 单向链表也称作是单链表。每个节点包含有两个域，一个是信息域（元素域），另一个是链接域。链接指向的是链表中的下一个节点，最后 一个节点的链接指向的是一个空值

其中，表元素域elem 是用来存放具体的数据的 ，链接域next 是用来存放下一个节点的位置（python中的标识） 变量p 指向链表的头节点（或者称为首节点） 的位置，从p 触发能找到表中的任意节点

单链表的操作 （1）length() ————> 链表的长度 （2）travel() ————> 遍历整个链表 （3）add( item ) ———— > 链表的头部添加元素 append(item) ————> 链表的尾部添加元素

insert( pos , item) —————> 指定位置添加元素 remove(item) ————> 删除节点

search(item) ————> 查找节点是否存在 is_empty() ————> 判断链表是否为空

单链表功能的代码实现：

class Node(object): def __init__(self, element): self.element = element self.next = None class SingleLink(object)：#单链表的封装 def __init__(self): # 默认情况下链表为空， 没有任何元素 self.head = None def is_empty(self): """判断链表是否为空""" return self.head == None def __len__(self): """ 链表长度: 1. 如果当前链表为空， 直接返回0； 1. 如果当前链表不为空， 依次遍历链表的每一个元素，计算长度 """ if self.is_empty(): return 0 else: cur = self.head length = 0 while cur != None: length += 1 cur = cur.next return length def trvel(self): """遍历链表""" if not self.is_empty(): cur = self.head while cur.next != None: print(cur.element, end=',') cur = cur.next print(cur.element) else: print("空链表") def append(self, item): """ 尾部添加元素 1. 先判断链表是否为空，若是空链表，则将head指向新节点 2. 若不为空，则找到尾部，将尾节点的next指向新节点 """ node = Node(item) if self.is_empty(): self.head = node else: cur = self.head while cur.next != None: cur = cur.next cur.next = node def add(self, item): """ 头部添加元素 1. 先创建一个保存item值的节点 2. 将新节点的链接域next指向头节点，即head指向的位置 3. 将链表的头head指向新节点 """ node = Node(item) node.next = self.head self.head = node def insert(self, index, item): """ 指定位置添加元素 1. 若指定位置index为第一个元素之前，则执行头部插入 2. 若指定位置超过链表尾部，则执行尾部插入 3. 否则， 找到指定位置 """ if index <= 0: self.add(item) elif index >= len(self): self.append(item) else: node = Node(item) count = 0 # 当前位置 cur = self.head while count < index - 1: count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self, item): """ 删除指定元素的节点： 1 2 3 4 5 """ cur = self.head if cur.element == item : self.head = self.head.next else: while cur: if cur.element != item: cur= cur.next else: cur = cur.next break if __name__ == '__main__': # 实例化单链表对象 link = SingleLink() # 长度获取 print("链表长度: ", len(link)) # 遍历链表 link.trvel() print("链表是否为空? ", link.is_empty()) print("添加元素:") link.append(1) link.append(2) link.add(3) link.insert(1, 'hello') # 3 'hello' 1 2 # 长度获取 print("链表长度: ", len(link)) # 遍历链表 link.trvel() print("链表是否为空? ", link.is_empty())

运行结果为：

单向循环链表 单向循环链表实际上就是单向链表的变形，链表中的最后一个节点Next域不再为空（none）而是指向链表的头节点。 单向循环链表具有的操作： （1）length() ————> 链表的长度 （2）travel() ————> 遍历整个链表 （3）add( item ) ———— > 链表的头部添加元素 （4）append(item) —————> 链表的尾部添加元素 （5）insert(pos, item) ——————> 指定位置添加元素 （6）remove(item) ——————> 删除节点 （7）search(item) ——————> 查找结点是否存在 （8）is_empty() ————> 链表是否为空

三. 双向链表

定义 ： 每个节点有两个链接： 一个指向前一个节点，当此节点为第一个节点时指向空值；而另一个指向下一个节点。当此节点为最后一个节点时，指向空值

双向链表的操作： （1）length() ——————> 链表的长度 （2） travel() —————— > 遍历整个链表 （3） add(item) —————— > 链表的头部添加元素 （4） append(item) ——————> 链表的尾部添加元素 （5）insert(pos,item) ——————> 指定位置添加元素 （6） remove(item) ——————> 删除节点 （7）search(item) ——————> 查找的节点是否存在 （8）is_empty() ————> 链表是否为空

代码实现：

class Node(object): """ 双链表节点的封装 """ def __init__(self, element): self.element = element self.next = None self.prev = None class SingleLink(object): """ 双链表的封装 """ def __init__(self): # 默认情况下链表为空， 没有任何元素 self.head = None def is_empty(self): """判断链表是否为空""" return self.head == None def __len__(self): """ 链表长度: 1. 如果当前链表为空， 直接返回0； 1. 如果当前链表不为空， 依次遍历链表的每一个元素，计算长度 """ if self.is_empty(): return 0 else: cur = self.head length = 0 while cur != None: length += 1 cur = cur.next return length def trvel(self): """遍历链表""" if not self.is_empty(): cur = self.head while cur.next != None: print(cur.element, end=',') cur = cur.next print(cur.element) else: print("空链表") def append(self, item): """ 尾部添加元素 1. 先判断链表是否为空，若是空链表，则将head指向新节点 2. 若不为空，则找到尾部，将尾节点的next指向新节点 """ node = Node(item) if self.is_empty(): self.head = node else: cur = self.head while cur.next != None: cur = cur.next cur.next = node cur.prev = cur def add(self, item): """ 头部添加元素 1. 先创建一个保存item值的节点 2. 将新节点的链接域next指向头节点，即head指向的位置 3. 将链表的头head指向新节点 """ node = Node(item) if self.is_empty(): self.head = node else: node.next = self.head self.head.prev = node self.head = node def insert(self, index, item): """ 指定位置添加元素 1. 若指定位置index为第一个元素之前，则执行头部插入 2. 若指定位置超过链表尾部，则执行尾部插入 3. 否则， 找到指定位置 """ if index <= 0: self.add(item) elif index >= len(self): self.append(item) else: node = Node(item) count = 0 # 当前位置 cur = self.head while count < index - 1: count += 1 cur = cur.next node.prev = cur node.next = cur.next cur.next = node def remove(self, item): """ 删除指定元素的节点： 1 2 3 4 5 """ pre =None cur = self.head if cur.element == item: self.head = self.head.next else: while cur: if cur.element != item: pre = cur cur = cur.next else: pre.next = cur.next cur.prev = pre.next break if __name__ == '__main__': # 实例化单链表对象 link = SingleLink() # 长度获取 print("链表长度: ", len(link)) # 遍历链表 link.trvel() print("链表是否为空? ", link.is_empty()) print("添加元素:") link.append(1) link.append(2) link.add(3) link.insert(1, 'hello') # 3 'hello' 1 2 # 长度获取 print("链表长度: ", len(link)) # 遍历链表 link.trvel() print("链表是否为空? ", link.is_empty())