江苏龙网

  1. 主页 > 生活百科 > >

Python数据结构之链表详解( 三 )

链表


文章插图
 
使用 Python 实现算法如下：
def insert(self, index, data):count = -1current = self.head# 判断插入位置的合法性if index > self.length or index < 0:raise IndexError("SinglyLinkedList assignment index out of range")else:node = Node(data)while count < index:# 查找插入位置previous = currentcurrent = current.nextcount += 1# 插入新结点node.next = previous.nextprevious.next = nodeself.length += 1也可以利用上述思想，直接在链表中插入结点：
def insert_node(self, index, node):count = -1current = self.headif index > self.length or index < 0:raise IndexError("SinglyLinkedList assignment index out of range")else:while count < index:previous = currentcurrent = current.nextcount += 1node.next = previous.nextprevious.next = nodeself.length += 12.6 删除指定位置元素要删除链表中第 i ii 个结点，首先在单链表中找到删除位置的前一个结点 previous，指针 current 指向要删除的结点，将 previous 的指针域修改为待删除结点 current 的后继结点的地址，删除后的结点需动态的释放 。下图 (b) 中的粉色虚线表示删除结点 current 后的指针指向：

Python数据结构之链表详解

文章插图
 
使用 Python 实现算法如下：
def __delitem__(self, index):if index > self.length - 1 or index < 0:raise IndexError("SinglyLinkedList assignment index out of range")else:count = -1previous = self.headwhile count < index - 1:previous = previous.nextcount += 1current = previous.nextprevious.next = current.nextself.length -= 1del current在插入和删除操作中，都是先确定操作位置，然后再进行插入和删除操作，所以其时间复杂度均为O(n) 。由于算法在进行插入和删除操作时没有移动元素的位置，只是修改了指针链接，所以采用链表存储方式进行插入和删除操作要比顺序存储方式的效率高 。
2.7 其它一些有用的操作2.7.1 链表元素输出操作
将单链表转换为字符串以便进行打印，使用 str 函数调用对象上的 str 方法可以创建适合打印的字符串表示：
def __str__(self):s = "["current = self.head.nextcount = 0while current != None:count += 1s += str(current)current = current.nextif count < self.length:s += '-->'s += "]"return s2.7.2 删除指定元素
与删除指定位置元素略有不同，删除指定元素需要在链表中删除第一个具有与给定值相同数据元素的结点，其时间复杂度同样为O(n)：
def del_value(self, value):current = self.headprevious = self.headwhile current != None:if current.data =https://www.isolves.com/it/cxkf/yy/Python/2022-07-29/= value:previous.next = current.nextself.length -= 1del currentreturnelse:previous = currentcurrent = current.nextraise ValueError("The value provided is not present!")2.7.3 在链表尾部追加新元素
为了方便的在链表尾部追加新元素，可以实现函数 append：
def append(self, value):node = Node(value)current = self.headwhile current.next is not None:current = current.nextcurrent.next = nodeself.length += 1此算法的时间复杂度为O(n)，如果需要经常在链表尾部追加新元素，可以使用增加尾指针 tail 用于追踪链表的最后一个元素，利用尾指针在链表尾部追加新元素时间复杂度可以降至O(1) 。
3. 单链表应用接下来，我们首先测试上述实现的链表，以验证操作的有效性，然后利用实现的基本操作来实现更复杂的算法 。
3.1 单链表应用示例首先初始化一个链表 sllist，并在其中追加若干元素：
sllist = SinglyLinkedList()# 在链表末尾追加元素sllist.append('apple')sllist.append('lemon')# 在指定位置插入元素sllist.insert(0, 'banana')sllist.insert(2, 'orange')我们可以直接打印链表中的数据元素、链表长度等信息：
print('链表为：', sllist)print('链表长度为：', len(sllist))print('链表第0个元素为：', sllist[0])# 修改数据元素sllist[0] = 'pear'print('修改链表数据后：', sllist)以上代码输出如下：
链表为： [banana-->apple-->orange-->lemon] 链表长度为： 4 链表第0个元素为： banana 修改链表数据后： [pear-->apple-->orange-->lemon]
接下来，我们将演示在指定位置添加/删除元素、以及如何查找指定元素等：
# 在指定位置添加/删除结点sllist.insert(1, 'grape')print('在位置1添加grape后链表数据：', sllist)del(sllist[2])print('修改链表数据后：', sllist)# 删除指定元素sllist.del_value('pear')print('删除pear后链表数据：', sllist)sllist.append('watermelon')print('添加watermelon后链表数据：', sllist)


推荐阅读


上一篇：Android 使用git合入修改patch

下一篇：浏览器自动化框架沦为攻击者的工具