python数据结构3-链表

文章目录

链表1.为什么需要链表2.链表的定义 单向链表1.单向链表的定义2.节点的实现3.单链表的操作1）is_empty() 链表是否为空2）length() 链表长度3）travel() 遍历整个链表4）add(item) 链表头部添加元素5)append(item) 链表尾部添加元素6）insert(pos, item) 指定位置添加元素7）remove(item) 删除节点8）search(item) 查找节点是否存在 单链表总结 单向循环链表双向链表1)add(item) 链表头部添加2)append(item) 链表尾部添加3)insert(pos, item) 指定位置添加4）remove(item) 删除节点 双向链表总结

链表

1.为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

2.链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

单向链表

1.单向链表的定义

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

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

2.节点的实现

#单链表 class Node(object): '''节点''' def __init__(self,elem): self.elem = elem self.next = None

3.单链表的操作

1）is_empty() 链表是否为空

def is_empty(self): '''is_empty() 链表是否为空''' return self.__head is None

2）length() 链表长度

def length(self): '''链表长度''' # cur游标 用来遍历节点 # count 记录数量 cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count

3）travel() 遍历整个链表

def travel(self): '''遍历整个链表''' cur = self.__head while cur != None: print(cur.elem,end = "\t") cur = cur.next print()

4）add(item) 链表头部添加元素

def add(self,item): '''链表头部添加元素，"头插法"''' node = Node(item) node.next = self.__head self.__head = node

5)append(item) 链表尾部添加元素

def append(self,item): #创建节点 node = Node(item) #判断链表是否为空 if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next #循环退出时,cur指向最后一个节点 cur.next = node

6）insert(pos, item) 指定位置添加元素

def insert(self,pos,item): '''指定位置添加元素 :param pos 从0开始 ''' if pos <= 0: self.add(item) elif pos >(self.length()-1): #没有等号 self.append(item) else: node = Node(item) cur = self.__head count = 0 #记录移动到哪个位置 while count < (pos-1): #当循环退出后，cur指向pos-1位置 count += 1 cur = cur.next node.next = cur.next cur.next = node

7）remove(item) 删除节点

def remove(self,item): '''删除节点''' cur = self.__head pre = None count =0 #用来返回删除的值的下标 while cur != None: #循环内所有点都照顾到 count += 1 if cur.elem == item: #判断此节点是否是头节点 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next #删除的是最后一个节点，此时pre.next = None,满足 return count else: pre = cur cur = cur.next

8）search(item) 查找节点是否存在

def search(self,item): '''查找节点是否存在''' cur = self.__head while cur != None: #若为while cur.next != None:则最后一个节点比较不了 if cur.elem == item: return True #return是结束函数执行并返回值 else: cur = cur.next return False

单链表总结

#单链表 class Node(object): '''节点''' def __init__(self,elem): self.elem = elem self.next = None class SingleLinkList(object): '''单链表''' def __init__(self,node = None): #默认参数为None self.__head = node def is_empty(self): '''is_empty() 链表是否为空''' return self.__head is None def length(self): '''链表长度''' # cur游标 用来遍历节点 # count 记录数量 cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): '''遍历整个链表''' cur = self.__head while cur != None: print(cur.elem,end = "\t") cur = cur.next print() def add(self,item): '''链表头部添加元素，"头插法"''' node = Node(item) node.next = self.__head self.__head = node def append(self,item): '''链表尾部添加元素,"尾插法"''' 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 insert(self,pos,item): '''指定位置添加元素 :param pos 从0开始 ''' if pos <= 0: self.add(item) elif pos >(self.length()-1): #没有等号 self.append(item) else: node = Node(item) cur = self.__head count = 0 #记录移动到哪个位置 while count < (pos-1): #当循环退出后，cur指向pos-1位置 count += 1 cur = cur.next node.next = cur.next cur.next = node def remove(self,item): '''删除节点''' cur = self.__head pre = None count =0 #用来返回删除的值的下标 while cur != None: count += 1 if cur.elem == item: #判断此节点是否是头节点 if cur == self.__head: self.__head = cur.next #只有一个节点，此时self.__head == None,满足 else: pre.next = cur.next #删除的是最后一个节点，此时pre.next = None,满足 return count else: pre = cur cur = cur.next def search(self,item): '''查找节点是否存在''' cur = self.__head while cur != None: #若为while cur.next != None:则最后一个节点比较不了 if cur.elem == item: return True #return是结束函数执行并返回值 else: cur = cur.next return False if __name__ == '__main__': ll =SingleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.append(3) ll.append(4) ll.append(5) ll.insert(3,9) #1 2 3 9 4 5 ll.insert(-1,0) #0 1 2 3 9 4 5 ll.travel() ll.remove(4) ll.travel() print(ll.search(5)) ll.remove(0) ll.travel() ll.remove(5) ll.travel()

运行结果：

True 0 False 1 0 1 2 3 9 4 5 0 1 2 3 9 5 True 1 2 3 9 5 1 2 3 9

单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。 单向循环列表代码总结（思路与上面相似，只是多考虑一步循环）

#单向循环列表 class Node(object): '''结点''' def __init__(self,elem): self.elem = elem self.next = None class SingleCycleLinkList(object): '''单向循环链表''' def __init__(self,node = None): #默认参数为None self.__head = node if node: node.next = node def is_empty(self): '''is_empty() 链表是否为空''' return self.__head is None def length(self): '''链表长度''' if self.is_empty(): return 0 # cur游标 用来遍历节点 cur = self.__head # count 记录数量 count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): '''遍历整个链表''' if self.is_empty(): #空列表 return cur = self.__head while cur.next != self.__head: print(cur.elem,end = "\t") cur = cur.next #退出循环，cur指向尾结点，但尾结点的元素未打印 print(cur.elem) def add(self,item): '''链表头部添加元素，"头插法"''' node = Node(item) if self.is_empty(): #空的为True self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # 退出循环，cur指向尾结点 node.next = self.__head self.__head = node cur.next = node def append(self,item): '''链表尾部添加元素,"尾插法"''' node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # 退出循环，cur指向尾结点 cur.next = node node.next = self.__head def insert(self,pos,item): '''指定位置添加元素 :param pos 从0开始 ''' if pos <= 0: self.add(item) elif pos >(self.length()-1): #没有等号 self.append(item) else: node = Node(item) pre = self.__head count = 0 #记录移动到哪个位置 while count < (pos-1): #当循环退出后，pre指向pos-1位置 count += 1 pre = pre.next node.next = pre.next pre.next = node def remove(self,item): '''删除节点''' if self.is_empty(): return cur = self.__head pre = None while cur.next != self.__head: if cur.elem == item: #判断此节点是否是头节点 if cur == self.__head: #头节点的情况 #找尾节点 rear = self.__head #新的游标 while rear.next != self.__head: rear = rear.next self.__head = cur.next rear.next = self.__head #中间节点 else: pre.next = cur.next return else: pre = cur cur = cur.next #退出循环，cur指向尾结点 if cur.elem == item: if cur == self.__head: #链表只有一个节点 self.__head = None else: pre.next = cur.next def search(self,item): '''查找节点是否存在''' if self.is_empty(): return False cur = self.__head while cur.next != self.__head: if cur.elem == item: return True #return是结束函数执行并返回值 else: cur = cur.next ## 退出循环，cur指向尾结点 if cur.elem == item: return True return False if __name__ == '__main__': ll =SingleCycleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.append(3) ll.append(4) ll.append(5) ll.insert(3,9) ll.insert(-1,0) ll.travel() ll.remove(4) ll.travel() print(ll.search(5)) ll.remove(0) ll.travel() ll.remove(5) ll.travel()

运行结果：

True 0 False 1 0 1 2 3 9 4 5 0 1 2 3 9 5 True 1 2 3 9 5 1 2 3 9

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。 后继结点：next 前驱结点：prev 双向链表与单链表一样的方法可以继承

1)add(item) 链表头部添加

def add(self,item): '''链表头部添加元素，"头插法"''' node = Node(item) node.next = self.__head self.__head.prev = node self.__head = node

2)append(item) 链表尾部添加

def append(self,item): '''链表尾部添加元素,"尾插法"''' node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur

3)insert(pos, item) 指定位置添加

def insert(self,pos,item): '''指定位置添加元素 :param pos 从0开始 ''' if pos <= 0: self.add(item) elif pos >(self.length()-1): #没有等号 self.append(item) else: node = Node(item) cur = self.__head count = 0 #记录移动到哪个位置 while count < pos: count += 1 cur = cur.next # 当循环退出后，cur指向pos位置 node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node

4）remove(item) 删除节点

def remove(self,item): '''删除节点''' cur = self.__head while cur != None: if cur.elem == item: #判断此节点是否是头节点 if cur == self.__head: self.__head = cur.next if cur.next: #判断链表是否只有一个结点 cur.next.prev = None else: cur.prev.next = cur.next if cur.next: #判断是不是最后一个结点 cur.next.prev = cur.prev break else: cur = cur.next

双向链表总结

#双向链表 class Node(object): '''结点''' def __init__(self,item): self.elem = item self.next = None self.prev = None class DoubleLinkList(object): '''双链表''' def __init__(self,node = None): #默认参数为None self.__head = node def is_empty(self): '''is_empty() 链表是否为空''' return self.__head is None def length(self): '''链表长度''' # cur游标 用来遍历节点 cur = self.__head # count 记录数量 count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): '''遍历整个链表''' cur = self.__head while cur != None: print(cur.elem,end = "\t") cur = cur.next print() def add(self,item): '''链表头部添加元素，"头插法"''' node = Node(item) node.next = self.__head self.__head.prev = node #与下面第二行作用一样 self.__head = node # node.next.prev = node def append(self,item): '''链表尾部添加元素,"尾插法"''' node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur def insert(self,pos,item): '''指定位置添加元素 :param pos 从0开始 ''' if pos <= 0: self.add(item) elif pos >(self.length()-1): #没有等号 self.append(item) else: node = Node(item) cur = self.__head count = 0 #记录移动到哪个位置 while count < pos: count += 1 cur = cur.next # 当循环退出后，cur指向pos位置 node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self,item): '''删除节点''' cur = self.__head while cur != None: if cur.elem == item: #判断此节点是否是头节点 if cur == self.__head: self.__head = cur.next if cur.next: #判断链表是否只有一个结点 cur.next.prev = None else: cur.prev.next = cur.next if cur.next: #判断是不是最后一个结点 cur.next.prev = cur.prev break else: cur = cur.next def search(self,item): '''查找节点是否存在''' cur = self.__head while cur != None: #若为while cur.next != None:则最后一个节点比较不了 if cur.elem == item: return True #return是结束函数执行并返回值 else: cur = cur.next return False if __name__ == '__main__': dll = DoubleLinkList() print(dll.is_empty()) print(dll.length()) dll.append(1) print(dll.is_empty()) print(dll.length()) dll.append(2) dll.append(3) dll.append(4) dll.append(5) dll.travel() dll.insert(3,9) #1 2 3 9 4 5 dll.insert(-1,0) #0 1 2 3 9 4 5 dll.travel() dll.remove(4) dll.travel() print(dll.search(5)) dll.remove(0) dll.travel() dll.remove(5) dll.travel()

运行结果：

True 0 False 1 1 2 3 4 5 0 1 2 3 9 4 5 0 1 2 3 9 5 True 1 2 3 9 5 1 2 3 9