大家有没有遇到过这些场景:
问: 请你说下 LinkedeList和ArrayList的区别?
答: ArrayList是Array(动态数组)的数据结构,LinkedList是Link(链表)的数据结构
所以了解链表的基础知识对于熟悉其它知识的原理是有一定帮助的
链表基础知识可以参考这篇文章, 讲得比较详细(为了不重复造轮子)
https://juejin.cn/post/6855865111354851335#heading-2
linked_struct.py 这是自定义的基础链表结构
class ListNode: # 定义结点
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __str__(self):
return str(self.val)
class SingleLinkList: # 定义链表结构
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def append(self, item):
node = ListNode(item)
if self.is_empty():
self.head = node
else:
cur = self.head
# 找到链表的尾部
while cur.next is not None:
cur = cur.next
cur.next = node
def length(self) -> int: # 获取链表长度
count = 0
cur = self.head
while cur is not None:
count += 1
cur = cur.next
return count
def view_linklist(self): # 遍历列表
dummy = ListNode()
dummy.next = self.head
while dummy.next is not None:
if dummy.next.next is None:
print(dummy.next.val)
else:
print(dummy.next.val, end=" -> ")
dummy = dummy.next
linked_test.py 这是上面 自定义的基础链表结构 的使用示例
from leetcode.linked_struct import ListNode
from leetcode.linked_struct import SingleLinkList
link_list = SingleLinkList()
# 定义6个链表结点
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)
# 定义链表的头结点(head)
link_list.head = node1
# 自定义添加链表结点 - 第1种方式
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
# 遍历链表, 输出元素
link_list.view_linklist() # 1 -> 2 -> 3 -> 4 -> 5 -> 6
print(link_list.length()) # 6
# 自定义添加链表结点 - 第2种方式
node7 = ListNode(7)
link_list.append(node7)
link_list.view_linklist() # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
print(link_list.is_empty()) # False
print(link_list.length()) # 7