数据结构——链表
一.简介
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。由一系列节点组成的元素集合。每个节点包含两部分，
数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表。链表中的每个节点包括两个部分：一个是存储数据元素的数据域；另一个是存储下一个节点的地址的指针域
双向链表：双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。
二.Python实现
♦链表节点
class Node: def __init__(self, item=None): self.item = item self.next = None
♦单向链表
class SingleLinkedList: """ 单向链表 """ def __init__(self, heda=None): self._head = heda self.length = 0
♦添加节点
头插法：从链表的头部（左端）插入
def add_head(self, element): """ 头插法：从头部插入 :param element: 需要添加进去的元素 :return: """ node = Node(element) if self._head is None: self._head = node else: node.next = self._head self._head = node self.length += 1
尾插法：从链表的尾部（右端）插入
def add_tail(self, element): """ 尾插法：从尾部添加元素 :param element:需要添加进去的元素 :return: """ # 创建一个节点 node = Node(element) if self._head is None: self._head = node else: cur = self._head # cur=node,node.next=None while cur.next: cur = cur.next cur.next = node return cur.next self.length += 1
♦插入节点
def insert(self, item: Node, index: int): """ 往链表中指定位置插入值 :param item: 插入的节点 :param index: 插入的位置 :return: """ if index < 0 or index > self.length: print('index out of range') return # 构建节点 if isinstance(item, Node): node_insert = item else: node_insert = Node(item) if index == 0: node_insert.next = self._head self._head = node_insert else: # 找到index的前一个节点 pre = self._head for i in range(self.length): if i == index - 1: node_insert.next = pre.next pre.next = node_insert break pre = pre.next self.length += 1 return
♦删除节点
def delete(self, index: int): """ 删除指定位置的节点 :param index: 节点的位置 :return: """ # 判空 if self.is_empty(): print('empty chain') return if index < 0 or index > self.length: print('index out of range') return if index == 0: self._head = self._head.next else: pre = self._head for i in range(self.length): if i == index - 1: pre.next = pre.next.next break pre = pre.next self.length -= 1 return
♦修改节点
def update(self, item, index: int): """ 修改节点item值 :param item: 修改之后的值 :param index:节点的位置 :return: """ # 判空 if self.is_empty(): print('empty chain') return if index < 0 or index >= self.length: print('index out of range') return node = self._head for i in range(self.length): if i == index: node.item = item return node = node.next
♦获取节点
def get_item(self, index: int): """ 获取指定位置的节点item :param index:指定位置 :return:item """ # 判空 if self.is_empty(): print('empty chain') return if index < 0 or index >= self.length: print('index out of range') return node = self._head for i in range(self.length): if i == index: return node.item node = node.next
♦遍历链表
def traversal(self): """链表遍历""" if self._head is None: return else: cur = self._head while cur: print(cur.item) cur = cur.next
♦反转链表
def reverse(self): """ 单向链表的反转：Input:1>2>3>4>5 Output:5>4>3>2>1 :return: """ if self._head is None or self.size() == 1: return else: pre = None cur = self._head while cur is not None: post = cur.next cur.next = pre pre = cur cur = post self._head = pre # 逆向后的头节点 self.traversal()
♦双向链表
class Node: def __init__(self, item=None): self.item = item self.next = None self.prior = None
♦双链表节点删除
♦双链表节点插入
1 class Node: 2 def __init__(self, item=None): 3 self.item = item 4 self.next = None 5 self.prior = None 6 7 8 class SingleLinkedList: 9 """ 10 单向链表 11 """ 12 13 def __init__(self, heda=None): 14 self._head = heda 15 self.length = 0 16 17 def is_empty(self): 18 """判断是否为空""" 19 return self.length == 0 20 21 def add_tail(self, element): 22 """ 23 尾插法：从尾部添加元素 24 :param element:需要添加进去的元素 25 :return: 26 """ 27 # 创建一个节点 28 node = Node(element) 29 if self._head is None: 30 self._head = node 31 else: 32 cur = self._head 33 # cur=node,node.next=None 34 while cur.next: 35 cur = cur.next 36 cur.next = node 37 return cur.next 38 self.length += 1 39 40 def add_head(self, element): 41 """ 42 头插法：从头部插入 43 :param element: 需要添加进去的元素 44 :return: 45 """ 46 node = Node(element) 47 if self._head is None: 48 self._head = node 49 else: 50 node.next = self._head 51 self._head = node 52 self.length += 1 53 54 def size(self): 55 56 """ 57 获取链表的大小 58 ：return：int 59 """ 60 count = 0 61 if self._head is None: 62 return count 63 64 else: 65 cur = self._head 66 while cur is not None: 67 count += 1 68 cur = cur.next 69 return count 70 71 def insert(self, item: Node, index: int): 72 """ 73 往链表中指定位置插入值 74 :param item: 插入的节点 75 :param index: 插入的位置 76 :return: 77 """ 78 if index < 0 or index > self.length: 79 print('index out of range') 80 return 81 # 构建节点 82 if isinstance(item, Node): 83 node_insert = item 84 else: 85 node_insert = Node(item) 86 if index == 0: 87 node_insert.next = self._head 88 self._head = node_insert 89 else: 90 # 找到index的前一个节点 91 pre = self._head 92 for i in range(self.length): 93 if i == index - 1: 94 node_insert.next = pre.next 95 pre.next = node_insert 96 break 97 pre = pre.next 98 self.length += 1 99 return100 101 def delete(self, index: int):102 """103 删除指定位置的节点104 :param index: 节点的位置105 :return:106 """107 # 判空108 if self.is_empty():109 print('empty chain')110 return111 if index < 0 or index > self.length:112 print('index out of range')113 return114 115 if index == 0:116 self._head = self._head.next117 else:118 pre = self._head119 for i in range(self.length):120 if i == index - 1:121 pre.next = pre.next.next122 break123 pre = pre.next124 self.length -= 1125 return126 127 def update(self, item, index: int):128 """129 修改节点item值130 :param item: 修改之后的值131 :param index:节点的位置132 :return:133 """134 # 判空135 if self.is_empty():136 print('empty chain')137 return138 if index < 0 or index >= self.length:139 print('index out of range')140 return141 142 node = self._head143 for i in range(self.length):144 if i == index:145 node.item = item146 return147 node = node.next148 149 def get_item(self, index: int):150 """151 获取指定位置的节点item152 :param index:指定位置153 :return:item154 """155 # 判空156 if self.is_empty():157 print('empty chain')158 return159 if index < 0 or index >= self.length:160 print('index out of range')161 return162 163 node = self._head164 for i in range(self.length):165 if i == index:166 return node.item167 node = node.next168 169 def traversal(self):170 """链表遍历"""171 if self._head is None:172 return173 else:174 cur = self._head175 while cur:176 print(cur.item)177 cur = cur.next178 179 def reverse(self):180 """181 单向链表的反转：Input:1>2>3>4>5182 Output:5>4>3>2>1183 思路：先将head.next断开，即指向断开的元素pre（none）;再将pre赋值head，将head赋值head.next;最后将head赋值pre184 :return:185 """186 if self._head is None or self.size() == 1:187 return188 else:189 pre = None190 cur = self._head191 while cur is not None:192 post = cur.next193 cur.next = pre194 pre = cur195 cur = post196 self._head = pre # 逆向后的头节点197 self.traversal()