大理网站制作公司,广东省白云区,广东网页空间网站平台,一建 专业Python3 实现单向链表
链表定义与简介
定义#xff1a;链表与顺序表(Python中列表)性质相反#xff0c;链表是物理单元上非顺序的、非连续的#xff0c;在逻辑顺序上其数据元素是通过指针实现的#xff0c;组成链表的每一个元素也可以叫做链表的节点#xff0c;节点可以…Python3 实现单向链表
链表定义与简介
定义链表与顺序表(Python中列表)性质相反链表是物理单元上非顺序的、非连续的在逻辑顺序上其数据元素是通过指针实现的组成链表的每一个元素也可以叫做链表的节点节点可以在运行时动态生成 单向链表中所有的元素也可以称之为节点每个节点包含两个区域如上图item区域称为数据域next区域为指针域单向链表中尾节点的判断只需判断该节点的指针(next)是否指向空即可。
链表(Linked list)与顺序表(Sequence list)的主要差异
顺序表的内存地址是连续的其数据元素有对应唯一的索引搜索时非常方便但进行元素插入时较麻烦每次插入元素其后所有元素都要移动一位。而链表内存地址是非连续、非顺序的逻辑顺序由指针实现在插入元素时只需将指定位置的前一个元素的指针断开并指向要插入的元素的节点然后插入的元素指针再指向下一个节点即可但是在查询元素时需要从头结点开始一个一个遍历寻找。
由于链表不是必须按顺序存储链表在插入的时候可以达到O(1)的复杂度比线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要O(n)的时间而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
定义单链表
# 定义节点
class Node:def __init__(self, item):self.item itemself.next None# 定义链表
class SingleLinkList:def __init__(self):self._head Noneif __name__ __main__:# 创建链表link_list SingleLinkList()# 创建结点node1 Node(1)node2 Node(2)# 将结点添加到链表link_list._head node1# 将第一个结点的next指针指向下一结点node1.next node2# 访问链表print(head, link_list._head) # 访问第一个结点数据print(link_list._head.item) # 访问第一个结点数据print(link_list._head.next.item) # 访问第二个结点数据一个简单的链表没有增删改查等功能操作十分不便
接下来对其进行一部分常用功能实现
清空元素clear()断开头结点的指针长度为0展示元素的值show_items()获取元素get_value_by_index()以偏移量获取元素的值超出偏移量会报错IndexErorr可以是负偏移判断链表是否为空is_empty()返回链表长度length()在指定位置插入insert()当超过实际长度在最后插入当为负数倒序选择插入负数的绝对值大于实际长度则在最前面插入在末尾追加元素append()指定偏移量移除元素remove()超过偏移量抛出IndexErorr可以使用负偏移判断一个元素是否存在于链表is_exist()存在返回True否则返回False返回元素的偏移indexOf()
代码实现
class Node:The nodes of single linked listdef __init__(self, item):self.item itemself.next Noneclass SingleLinkedList:def __init__(self):Initialize the head and the length of single linked listself.head Nonedef clear(self):CLear a linked listself.head Nonedef show_items(self):Show all the elements of linked listif self.is_empty():return Nonecur self.headwhile cur.next:yield cur.itemcur cur.nextyield cur.itemdef get_value_by_index(self, index):Get a value by indexnode self.headindex self.length()index if index 0 else indexif index 0:raise IndexError(index out of range)try:for i in range(index):node node.nextreturn node.itemexcept AttributeError as e:raise IndexError(index out of range)def is_empty(self):Judge if a linked list is emptyreturn self.head is Nonedef length(self):Return the elements number of a linked listcur self.headif not cur:return 0count 1while cur.next:count 1cur cur.nextreturn countdef insert(self, index, item):Insert an element before the given index of a nodenode Node(item)length self.length()# Empty list, append directlyif not self.head:self.append(item)if index 0 and (index length) 0:index length# index0if index 0:cur self.headwhile cur.next:if index 1:breakcur cur.nextindex - 1node.next cur.nextcur.next nodeelif index 0 or index length 0:temp self.headnode.next tempself.head nodedef append(self, item):Append elements to the end of a linked listnode Node(item)if self.is_empty():self.head nodeelse:cur self.headwhile cur.next:cur cur.nextcur.next nodedef remove(self, index):Remove an element by indexif not -self.length() - 1 index self.length():raise IndexError(remove index out of range)if index 0:index self.length()print(findex, index)if index 0:print(Get into )self.head self.head.nextelse:cur self.headpre curwhile index 0:pre curcur cur.nextindex - 1pre.next cur.nextdef is_exist(self, item):Judge if an element in linked-listreturn item in self.show_items()def indexOf(self, item):Return a given items index where is the first appearance in the listreturn list(self.show_items()).index(item)验证功能
if __name__ __main__:SLL SingleLinkedList()print(fIf the linked list is empty?: {SLL.is_empty()})# Append elements to the endfor i in range(5):SLL.append(i)print(fShow all items:{list(SLL.show_items())})print(fThe length of {SLL.__class__.__name__}: {SLL.length()})# _index0_index, _item 9, 11SLL.insert(_index, _item)print(fInsert {_item} before linked list[{_index}]: {list(SLL.show_items())})# _index0_index, _item 0, 22SLL.insert(_index, _item)print(fInsert {_item} before linked list[{_index}]: {list(SLL.show_items())})# _index0 and length_index0_index, _item -3, 33SLL.insert(_index, _item)print(fInsert {_item} before linked list[{_index}]: {list(SLL.show_items())})# _index0 and length_index0_index, _item -21, 44SLL.insert(_index, _item)print(fInsert {_item} before linked list[{_index}]: {list(SLL.show_items())})_index -5SLL.remove(_index)print(fRemove an element by index[{_index}]: {list(SLL.show_items())})# Get a value by index, if index out of range, throw a IndexError_index 3print(fGet a value by index[{_index}], its value: {SLL.get_value_by_index(3)})_item 44print(fIf item:[{_item}] in linked list {SLL.__class__.__name__}? {SLL.is_exist(_item)} )# CLear a linked listprint(fThe linked list has been cleared: {SLL.__class__.__name__}: {SLL.clear()})print(fThe length of {SLL.__class__.__name__}: {SLL.length()})结果
If the linked list is empty?: True
Show all items:[0, 1, 2, 3, 4]
The length of SingleLinkedList: 5
Insert 11 before linked list[9]: [0, 1, 2, 3, 4, 11]
Insert 22 before linked list[0]: [22, 0, 1, 2, 3, 4, 11]
Insert 33 before linked list[-3]: [22, 0, 1, 2, 33, 3, 4, 11]
Insert 44 before linked list[-21]: [44, 22, 0, 1, 2, 33, 3, 4, 11]
Remove an element by index[-5]: [44, 22, 0, 1, 33, 3, 4, 11]
Get a value by index[3], its value: 1
If item:[44] in linked list SingleLinkedList? True
The linked list has been cleared: SingleLinkedList: None
The length of SingleLinkedList: 0
