数据结构与算法--单向链表

阅读目录

单向链表概念python中变量的本质游标（指针）的理解节点的实现如何输出节点单向链表的操作单向链表分步实现单向链表完整实现单向链表和顺序表的对比常见三种链表的比较

单向链表

概念

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

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

python中变量的本质

''' a=10;a=f();前者只会保存内存地址，后者才回去申请空间来存储数据； 和别的语言不通，别的语言变量名就是存储的别名 '''

总结： 空节点/虚拟的节点 指向 头节点，它也可以指向任意一个位置 一个节点的链接区 = 下一个节点 如：cur.next=下一个节点； 所以空节点链接区：self.__head = 头节点 （一般情况） 尾节点的链接区=None

游标（指针）的理解

''' cur移动时停留在节点上，cur.next表示当前停留节点上的next链接域，它指向下一个节点， 也就是说：cur.next=下一个节点 '''

节点的实现

# 单链表的结点 class SingleNode(object): def __init__(self, item): # item存放数据元素 self.item = item # next是下一个节点的标识 self.next = None

如何输出节点

class Node(object): def __init__(self, item): self.item = item self.next = None def print_link(node): while node: print(node.item) node = node.next if __name__ == '__main__': n1 = Node(1) # 先将节点链接起来 n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 # n3.next = None 这句话可以省略，没写默认指向None print_link(n1) # 打印默认 输入头节点

单向链表的操作

''' is_empty() 链表是否为空 length() 链表长度 travel() 遍历整个链表 add(item) 链表头部添加元素 append(item) 链表尾部添加元素 insert(pos, item) 指定位置添加元素 remove(item) 删除节点 search(item) 查找节点是否存在 '''

单向链表分步实现

class Node(object): # 节点 def __init__(self, item): self.elem = item # 元素区 self.next = None # 指针区 class SingleLinkList(object): # 单链表 def __init__(self,node=None): # 不传节点，就默认为空 self.__head = node # 虚节点（P变量）；设为私有 def is_empty(self): # 判断链表是否为空 return self.__head == None # 返回正则表达式 # 链表长度 def length(self): # cur初始时指向头节点 cur = self.__head # 为空链表时，cur=None,进不了循环，直接返回0了 count = 0 # 等于0是最好的选择 # 当未到达尾部时，尾节点是指向None while cur != None: count += 1 # 将cur后移一个节点 cur = cur.next # 将当前节点 往后移一个节点 return count

# 遍历链表 def travel(self): if self.is_empty(): return cur = self.__head while cur != None: print(cur.item, end=" ") cur = cur.next print(" ") # 尾部添加元素（尾插法） def append(self, item): # 这个item是元素具体数据，而不是节点，节点会用类帮助封装 node = Node(item) # 实例一个节点 # 先判断链表是否为空，若是空链表，则将_head指向新节点 if self.is_empty(): # 调用判断函数 self.__head = node # 直接让虚拟节点，指向新节点 # 若不为空，则找到尾部，将尾节点的next指向新节点 else: cur = self.__head while cur.next != None: cur = cur.next # 直到走到尾结点 cur.next = node # 让尾结点指针区连接上新节点 # 头部添加元素（头插法） # 步骤：先让新节点指针指向头节点，再让头节点指针指向新节点 def add(self, item): # 原有链表是空链表也满足 """头部添加元素""" # 先创建一个保存item值的节点 node = Node(item) # 将新节点的链接域next指向头节点，即__head指向的位置 node.next = self.__head # 先完成这一步，保证原有不先断开 # 将链表的头__head指向新节点 self.__head = node

# 指定位置添加元素 def insert(self, pos, item): """指定位置添加元素""" # 若指定位置pos为第一个元素之前，则执行头部插入 if pos <= 0: self.add(item) # 若指定位置超过链表尾部，则执行尾部插入 elif pos > (self.length() - 1): self.append(item) # 找到指定位置 else: # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置 pre = self.__head count = 0 while count < (pos - 1): count += 1 pre = pre.next # 先将新节点node的next指向插入位置的节点 node = Node(item) node.next = pre.next # 头节点的下一个节点 # 将插入位置的前一个节点的next指向新节点 pre.next = node

# 查找节点是否存在 def search(self, item): """链表查找节点是否存在，并返回True或者False""" cur = self.__head while cur != None: # 这里是cur而不是cur.next,后者会忽略去比对最后一个节点元素 if cur.item == item: return True cur = cur.next # 让游标移动一个位置 return False # 删除节点 def remove(self, item): if self.is_empty(): return cur = self.__head pre = None while cur != None: # 遍历查找，一直移动到尾节点 # 找到了指定元素 if cur.item == item: # 如果不为空，而且第一个就是删除的节点 if not pre: # 将头指针指向头节点的后一个节点 self._head = cur.next else: # 将删除位置前一个节点的next，指向删除位置的后一个节点 pre.next = cur.next break # 记得删除完退出 else: # 继续按链表后移节点 pre = cur cur = cur.next

单向链表完整实现

class Node(object): # 节点：元素和指针 def __init__(self, item): self.elem = item self.next = None class SingleLinkList(object): # 单链表 def __init__(self, node=None): self.__head = node def is_empty(self): # 是否为空链表 return self.__head == None def length(self): # 单链表的长度 cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): # 遍历 if self.is_empty(): return cur = self.__head while cur != None: print(cur.item, end=" ") cur = cur.next print(" ") # 遍历 法二： ''' def travel(self): if self.is_empty(): return cur = self.__head while cur.next != None: # 表示节点必须大于1个 print(cur.item, end=" ") cur = cur.next print(cur.item) # 注意这里，打印只有一个节点的情况 ''' 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): if pos <= 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: pre = self.__head count = 0 while count < (pos - 1): count += 1 pre = pre.next node = Node(item) node.next = pre.next pre.next = node def search(self, item): cur = self.__head while cur != None: if cur.elem == item: return True cur = cur.next return False def remove(self, item): pre = None cur = self.__head while cur != None: if cur.elem == item: if pre == None: self.__head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next if __name__ == '__main__': s = SingleLinkList() print(s.is_empty()) # True print(s.length()) # 0 s.append(1) print(s.is_empty()) # False print(s.length()) # 1 s.append(4) s.append(5) s.append(6) s.append(8) s.add(88) s.insert(-1, 111) s.insert(10, 999) s.insert(3, 222) print(s.search(999)) # True s.travel() # 111 88 1 222 4 5 6 8 999 s.remove(111) s.travel() # 88 1 222 4 5 6 8 999 s.remove(222) s.travel() # 88 1 4 5 6 8 999 s.remove(999) s.travel() # 88 1 4 5 6 8

单向链表和顺序表的对比

''' 单向链表和顺序表的对比： 链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大， 但对存储空间的使用要相对灵活。 链表与顺序表的各种操作复杂度如下所示： 操作 链表 顺序表 访问元素 O(n) O(1) 在头部插入/删除 O(1) O(n) 在尾部插入/删除 O(n) O(1) 在中间插入/删除 O(n) O(n) 注意： 虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。 链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。 顺序表查找很快，主要耗时的操作是拷贝覆盖。 因为除了目标元素在尾部的特殊情况， 顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作， 只能通过拷贝和覆盖的方法进行。 '''

常见三种链表的比较