(一)数组
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
1、数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。
通过 a[i]_address = a[0]_address + i*元素的大小(字节) ,得到a[i]所在的位置。
2、插入:
数组长度为n,在索引k插入一个元素,k~n的元素都需要向后搬移。时间复杂度为O(n) 。(在末尾插入时间复杂度O(1),首位插入则为O(n),平均时间复杂度为O(n))
如果数组是无序的,可以在末尾插入,再和第k个元素互换,实现O(1)时间复杂度复杂度的插入。
3、删除
和插入类似。数组长度为n,删除第k个元素,则k+1~n的元素都需要向前搬移一位,时间复杂度为o(n)。
如果数组是无序的,可以将末尾的元素和第k个元素互换位置,然后再删除,实现O(1)时间复杂度的删除。
(二)链表
1、数组与链表在底层存储结构上的区别
(1)数组需要一段连续的内存空间,链表则不需要
(2)链表通过“指针”,将一组零散的内存空间串联在一起。
2、常用的链表结构
(1)单链表
(2)双向链表
(3)循环链表
3、单链表
(1)把内存块(data)称为链表的“结点”,用于存储数据。next记录下一个节点的内存地址,把这个记录下个结点地址的指针称为后继指针next。
(2)第一个结点称为头结点,最后一个结点称为尾结点。尾结点的指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表的最后一个结点。
(3)链表插入、删除的时间复杂度O(1),只需要修改指针即可。
(4)链表随机访问的时间复杂度是O(n)。因为链表的内存空间是零散的,没法像数组那样通过简单的寻址公式实现随机访问,只能一个一个结点依次遍历,直到找到相应的结点。
4、循环链表
和单链表唯一的区别就在于尾结点,尾结点的指针指向头结点,而不是空地址。
5、双向链表
(1)相比单链表,多了一个前驱指针,指向前一个结点
(三)练习题
1、单链表反转。 leetcode : 206
1 # 迭代方式
2 class ListNode:
3 def __init__(self, x):
4 self.val = x
5 self.next = None
6
7 class Solution:
8 def reverseList(self, head: ListNode) -> ListNode:
9 if head is None or head.next is None:
10 return head
11 prev_node = None
12 while head is not None:
13 next_node = head.next # 备份下一结点的内存地址
14 head.next = prev_node # 当前结点的指针指向前一结点(头结点指向None)
15 prev_node = head # 更新前一结点的值。
16 head = next_node # 设置当前结点为下一结点的地址
17 return prev_node
18
19 if __name__ == "__main__":
20 l1 = ListNode(1)
21 l1.next = ListNode(2)
22 l1.next.next = ListNode(3)
23 l1.next.next.next = ListNode(4)
24 l1.next.next.next.next = ListNode(5)
25 rev_result = Solution().reverseList(l1)
26 for i in range(6):
27 if rev_result is not None:
28 print(rev_result.val)
29 rev_result = rev_result.next
30 else:
31 print(rev_result)
1 # 递归方式
2 class ListNode:
3 def __init__(self, x):
4 self.val = x
5 self.next = None
6
7 class Solution:
8 def reverseList(self, head: ListNode) -> ListNode:
9 if head is None or head.next is None:
10 return head
11 next_node = self.reverseList(head.next)
12 head.next.next = head
13 head.next = None
14 return next_node
15 """
16 递归和迭代不同的是,递归从后向前,迭代从前往后
17 1、 head.val = 4
18 4.next.next = head, 实际就是5的指针指向结点4的内存地址
19 4.next = None ,断开之前 4 -> 5 的指针
20 2、 head.val = 3
21 3.next.next = head, 实际就是4的指针指向结点3的内存地址
22 3.next = None , 断开之前 3 -> 4 的指针
23 ...
24 4: head.val = 1
25 1.next.next = head, 实际就是2的指针指向结点1的内存地址
26 1.next = None ,头结点指向None
27 """
28 if __name__ == "__main__":
29 l1 = ListNode(1)
30 l1.next = ListNode(2)
31 l1.next.next = ListNode(3)
32 l1.next.next.next = ListNode(4)
33 l1.next.next.next.next = ListNode(5)
34 rev_result = Solution().reverseList(l1)
35 for i in range(6):
36 if rev_result is not None:
37 print(rev_result.val)
38 rev_result = rev_result.next
39 else:
40 print(rev_result)
2、链表中环的检测: leetcode 141
1 # Definition for singly-linked list.
2 # class ListNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution:
8 def hasCycle(self, head: ListNode) -> bool:
9 flag = True
10 while head is not None:
11 next_node = head.next
12 if next_node is None: # 如果指针的值为None,表示没有环
13 return False
14 elif next_node == True: # 如果指针的值为True,表示有环
15 return True
16 head.next = flag # 将结点指针的值设置为True
17 head = next_node # head 设置为下一结点
18 return False
3、两个有序的链表合并,leetcode 21
1 # Definition for singly-linked list.
2 class ListNode:
3 def __init__(self, x):
4 self.val = x
5 self.next = None
6
7 class Solution:
8 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
9 new_node = ListNode("K")
10 move = new_node # 加一个move,是为了让new_node一直代表头结点,方便返回数据
11 while l1 and l2:
12 if l1.val > l2.val:
13 move.next = l2
14 l2 = l2.next
15 else:
16 move.next = l1
17 l1 = l1.next
18 move = move.next
19 move.next = l1 if l1 else l2
20 return new_node.next
21
22
23
24 if __name__ == "__main__":
25 l1 = ListNode(1)
26 l1.next = ListNode(2)
27 l1.next.next = ListNode(3)
28 l2 = ListNode(1)
29 l2.next = ListNode(3)
30 l2.next.next = ListNode(4)
31 result = Solution().mergeTwoLists(l1,l2)
32 for i in range(6):
33 print(result.val)
34 result = result.next
4、删除链表倒数第 n 个结点,leetcode 19
1 class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6 class Solution:
7 def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
8 new_node = ListNode("k") # 加一个哨兵,方便处理头结点
9 curson = head # 当前结点的指针
10 prev = new_node # 前一结点的指针
11 new_node.next = head
12 num = 0
13 while head: # 得到链表的长度
14 num += 1
15 head = head.next
16 for i in range(num):
17 if i == (num - n): # 删除第n个结点,并返回头结点
18 prev.next = curson.next
19 return new_node.next
20 prev = curson
21 curson = curson.next
22 return new_node.next
23
24 if __name__ == "__main__":
25 l1 = ListNode(1)
26 l1.next = ListNode(2)
27 l1.next.next = ListNode(3)
28 result = Solution().removeNthFromEnd(l1,3)
29 for i in range(10):
30 try:
31 print(result.val)
32 result = result.next
33 except:
34 pass
5、求链表的中间结点 leetcode 876
1 # Definition for singly-linked list.
2 # class ListNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.next = None
6
7 class Solution:
8 def middleNode(self, head: ListNode) -> ListNode:
9 curson = head
10 num = 0
11 while head: # 得到链表总长度
12 num += 1
13 head = head.next
14 idx = num // 2 # 得到中间结点
15 for i in range(num): # 返回中间结点
16 if i == idx:
17 return curson
18 curson = curson.next