赞
踩
目录
链表(Linked List):一种线性表数据结构。它使用一组任意的存储单元(可以是连续的,也可以是不连续的),来存储一组具有相同类型的数据。
数据结构的操作一般涉及到增、删、改、查 4 种情况,链表的操作也基本上是这 4 种情况。
链表是由链节点通过 next
链接而构成的,所以先来定义一个简单的链节点类,即 ListNode
类。ListNode
类使用成员变量 val
表示数据元素的值,使用指针变量 next
表示后继指针。
然后再定义链表类,即 LinkedList
类。ListkedList
类中只有一个链节点变量 head
用来表示链表的头节点。
我们在创建空链表时,只需要把相应的链表头节点变量设置为空链接即可。在 Python
里可以将其设置为 None:
- # 链节点类
- class ListNode:
- def __init__(self, val=0, next=None):
- self.val = val
- self.next = next
-
- # 链表类
- class LinkedList:
- def __init__(self):
- self.head = None
'运行
求线性链表的长度操作只需要使用一个可以顺着链表指针移动的指针变量 cur
和一个计数器 count
。具体做法如下:
cur
指向链表的第 1
个链节点。next
指针遍历链表,指针变量 cur
每指向一个链节点,计数器就做一次计数。cur
指向为空时结束遍历,此时计数器的数值就是链表的长度,将其返回即可。- # 获取链表长度
- def length(self):
- count = 0
- cur = self.head
- while cur:
- count += 1
- cur = cur.next
- return count
'运行
在链表中查找值为 val
的位置:链表不能像数组那样进行随机访问,只能从头节点 head
开始,沿着链表一个一个节点逐一进行查找。如果查找成功,返回被查找节点的地址。否则返回 None
。
- # 查找元素
- def find(self, val):
- cur = self.head
- while cur:
- if val == cur.val:
- return cur
- cur = cur.next
-
- return None
'运行
三种:
- # 头部插入元素
- def insertFront(self, val):
- node = ListNode(val)
- node.next = self.head
- self.head = node
- # 尾部插入元素
- def insertRear(self, val):
- node = ListNode(val)
- cur = self.head
- while cur.next:
- cur = cur.next
- cur.next = node
- # 中间插入元素
- def insertInside(self, index, val):
- count = 0
- cur = self.head
- while cur and count < index - 1:
- count += 1
- cur = cur.next
-
- if not cur:
- return 'Error'
-
- node = ListNode(val)
- node.next = cur.next
- cur.next = node
'运行
将链表中第 i
个元素值改为 val
:首先要先遍历到第 i
个链节点,然后直接更改第 i
个链节点的元素值。
- # 改变元素
- def change(self, index, val):
- count = 0
- cur = self.head
- while cur and count < index:
- count += 1
- cur = cur.next
-
- if not cur:
- return 'Error'
-
- cur.val = val
'运行
三种:
- # 链表头部删除元素
- def removeFront(self):
- if self.head:
- self.head = self.head.next
- # 链表尾部删除元素
- def removeRear(self):
- if not self.head.next:
- return 'Error'
-
- cur = self.head
- while cur.next.next:
- cur = cur.next
- cur.next = None
- # 链表中间删除元素
- def removeInside(self, index):
- count = 0
- cur = self.head
-
- while cur.next and count < index - 1:
- count += 1
- cur = cur.next
-
- if not cur:
- return 'Error'
-
- del_node = cur.next
- cur.next = del_node.next
'运行
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。