Pyhon3的链表的实现(包含遍历,读取,删除,头插,尾插)
还记得上次面试挂在了链表上,记忆忧新,最近特别赶工重新学习了数据结构等一系列知识,恶补自己的基础。今天趁着复习链表的时候,把Python的链表代码详细的讲解一遍。谢谢大家的支持。
进入正题,链表是一种数据结构,是一种典型的线性结构。它的存储的方式并不像顺序表那样,是按照顺序一个挨着一个放置的,它的每一个节点(就是存储在其中的一个元素单元)都不是相邻的,所以相对来讲,链表不需要一块完整的内存,但是由于每个节点都需要存储下一个节点的位置信息,所以所占用的内存,其实还会比较多一点,来一张图片理解一下吧。
很容易发现,顺序表中的单元,一个挨一个放置,而链表,需要多加一个元素来存放下一个的地址,所以,从这里我们可以推断出这两个结构的比较的一部分:
顺序表:
一、逻辑(下标)上相邻的元素物理(内存)上也相邻!
二、需要一整块的内存(由图很轻易就能知道,不连续就不是顺序表了)
三、读取简单(直接通过下标,解释器就能直接计算并寻址,时间复杂度为O(1))
链表:
一、不需要一整块内存,(因为每个节点(node)都是分开存放的)
二、逻辑上相邻的元素,其实并不相邻。
三、读取较难(因为需要从“头”开始,一个挨一个的顺序读,假设读第n个元素,就要寻址n次,时间复杂度为O(n))。
我们还从上图得到一个消息,我们每个节点有两个属性——本身的值,下一个节点的位置。
所以代码应该这么写:
class SingleNode(object):
"""单链表的节点"""
def __init__(self, elem):
self.elem = elem # 存放数据元素
self.next = None
很清晰吧,一个SingleNode的类,存放自己的值和下一个节点的位置,下一个节点默认为None。
接下来,继续讲链表:
在我们插入元素时,顺序表插入的同时需要把插入位置以及之后的元素都后移一位,我们弹出元素时,顺序表弹出后,需要把弹出元素之后的元素全部向前移动一位。这点相信大家都没有疑问,因为他是顺序表,所以必须按照顺序一个挨一个的存放,对吧。看图:
插入时,返回来,先移动后放入。
对于链表来讲,元素的插入和移除反而就不那么难了,因为我们的节点都是单独存在的,插入还是删除,都仅仅只需要修改两个地方的指向就可以了:
第一步:把新来的节点指向他前面那一个的节点指向的节点。
第二步:把前面那个节点指向新来的节点。
所以我们又概括出了顺序表和链表的不同:
顺序表:删除和插入需要耗费大量的时间去整理插入/删除后剩余的元素
链表:插入和删除非常快速。
在代码中怎么实现呢?
def add(self, item):
"""在头部添加元素, 头插法"""
node = SingleNode(item)
node.next = self.__head
self.__head = node
self.__length += 1
上面的是“头插法”,直接插在头节点和第一个元素之前,插完之后,新的节点是头节点后的第一个节点。
def append(self, item):
"""在尾部添加元素,尾插法"""
node = SingleNode(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
self.__length += 1
上面是“尾插法”,直接在链表最后插入一个新节点,插入之后,自己是最后一个节点,当然,插入之前,判断是否是空的。如果是空的,直接让头节点指向它即可。
虽然没有完整代码,我们可以从上面的片段中了解到:链表头插很快,尾插稍微慢了一点。
那么,有了一个链表,我们自然要输出,输出我们就可以从头节点开始,一直读取下一个,输出了 。
def travel(self):
"""遍历整个链表"""
cur = self.__head # 用来记录当前的节点
while cur != None:
print(cur.elem, end=' ')
cur = cur.next
print()
现在,我们大概已经有了一个思路,来看看全部的代码先:
class SingleNode(object):
"""单链表的节点"""
def __init__(self, elem):
self.elem = elem # 存放数据元素
self.next = None
class SingleLinkList(object):
"""单链表的类"""
def __init__(self, node=None):
self.__head = node
self.__length = 0
def is_empty(self): # 因为是对对象的一个操作,所以使用对象的self
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表长度"""
return self.__length
def travel(self):
"""遍历整个链表"""
cur = self.__head # 用来记录当前的节点
while cur != None:
print(cur.elem, end=' ')
cur = cur.next
print()
def read_next(self):
"""一次读一个"""
cur = self.__head # 用来记录当前的节点
while cur != None:
yield cur.elem
cur = cur.next
yield None
def add(self, item):
"""在头部添加元素, 头插法"""
node = SingleNode(item)
node.next = self.__head
self.__head = node
self.__length += 1
def insert(self, pos, item):
"""在指定的位置添加节点,:param pos 从0开始索引"""
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 # 当循环结束后,pre指向pos-1的位置
node = SingleNode(item) # 创建一个节点
node.next = pre.next
pre.next = node # 让pre指向这个节点
self.__length += 1
def append(self, item):
"""在尾部添加元素,尾插法"""
node = SingleNode(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
self.__length += 1
def remove(self, item):
"""删除节点"""
pre = None
cur = self.__head
while cur != None:
if cur.elem == item:
if pre == None: # 当pre为空时,说明还没开始即删除的首节点
self.__head = cur.next
self.__length -= 1
return # 删除之后退出
pre.next = cur.next
cur.next = None
self.__length -= 1
return # 删除之后退出
pre = cur
cur = cur.next
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
cur = cur.next
return False
代码大概如上,其中的大概上面已经讲完了,插入,删除,搜索,添加,然后是insert指定位置添加,包括使用生成器对象一个挨一个读取元素,下面贴上使用示例:
def 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.add(8)
ll.travel()
ll.length()
ll.insert(-1, 9)
ll.travel()
ll.insert(2, 90)
ll.travel()
ll.insert(20, 900)
ll.travel()
print(ll.length())
ll.remove(900)
ll.travel()
print(ll.length())
print(ll.search(90))
MyList1_num = ll.read_next()
num1 = next(MyList1_num)
print(num1)
if __name__ == "__main__":
main()
今天就到这里吧,谢谢大家的观看。