【数据结构】数组、双链表代码实现
【摘要】 文章目录🍋数组(Array)🍋链表(Linked List)🍋代码实现🍋总结🍋数组(Array)基本原理: 数组是一种线性数据结构,它在内存中是一段连续的存储空间。 数组通过索引(或下标)访问元素,索引从 0 开始递增。 所有元素的类型相同,占用的内存空间相等。优点: 随机访问:可以通过索引快速访问任意位置的元素,时间复杂度为 O(1)。 索引计算简单...
🍋数组(Array)
基本原理:
数组是一种线性数据结构,它在内存中是一段连续的存储空间。
数组通过索引(或下标)访问元素,索引从 0 开始递增。
所有元素的类型相同,占用的内存空间相等。
优点:
随机访问:可以通过索引快速访问任意位置的元素,时间复杂度为 O(1)。
索引计算简单:根据索引计算元素的内存地址很简单,只需一个乘法和一个加法操作。
缺点:
大小固定:数组的大小在创建时就固定了,无法动态调整。
插入和删除操作效率低:在数组中间插入或删除元素会涉及到大量元素的移动,时间复杂度为 O(n)。
内存空间的浪费:如果数组预留了很大的空间但只存储了少量元素,会造成内存空间的浪费。
🍋链表(Linked List)
基本原理:
链表是一种由节点组成的数据结构,每个节点包含数据和指向下一个节点的指针(或引用)。
节点不必在内存中连续存储,通过指针将它们串联起来。
优点:
动态大小:链表的大小可以动态增长或缩小,不需要预先分配固定大小的空间。
插入和删除操作高效:在链表中插入或删除元素只需要改变指针的指向,时间复杂度为 O(1)。
缺点:
随机访问低效:要访问链表中的第 k 个元素,需要从头节点开始依次遍历,时间复杂度为 O(k)。
需要额外的空间存储指针:每个节点都需要额外的空间存储指向下一个节点的指针,占用的内存空间较大。
🍋代码实现
数组
from selenium.common import NoSuchElementException
class MyArrayList:
def __init__(self, init_capacity=1):
self.data = [None] * init_capacity
self.size = 0
# 在列表末尾添加元素 e。
# 如果列表已满,则调用 _resize 函数扩展列表的容量。
def add_last(self, e):
cap = len(self.data)
if self.size == cap:
self._resize(2 * cap)
self.data[self.size] = e
self.size += 1
# 在指定索引 index 处插入元素 e。
# 如果列表已满,则调用 _resize 函数扩展列表的容量。
# 使用切片操作实现在 index 处插入元素,并将后续元素向后移动一个位置。
def add(self, index, e):
self._check_position_index(index)
cap = len(self.data)
if self.size == cap:
self._resize(2 * cap)
self.data[index+1:self.size+1] = self.data[index:self.size]
self.data[index] = e
self.size += 1
# 在列表开头添加元素 e,实际上是调用 add(0, e)。
def add_first(self, e):
self.add(0, e)
# 移除并返回列表末尾的元素。
# 如果列表的大小为容量的四分之一,则调用 _resize 函数缩小列表的容量。
def remove_last(self):
if self.size == 0:
raise NoSuchElementException()
cap = len(self.data)
if self.size == cap // 4:
self._resize(cap // 2)
deleted_val = self.data[self.size - 1]
self.data[self.size - 1] = None
self.size -= 1
return deleted_val
# 移除并返回指定索引 index 处的元素。
# 如果列表的大小为容量的四分之一,则调用 _resize 函数缩小列表的容量。
# 使用切片操作实现在 index 处移除元素,并将后续元素向前移动一个位置。
def remove(self, index):
self._check_element_index(index)
cap = len(self.data)
if self.size == cap // 4:
self._resize(cap // 2)
deleted_val = self.data[index]
self.data[index:self.size-1] = self.data[index+1:self.size]
self.data[self.size - 1] = None
self.size -= 1
return deleted_val
# 移除并返回列表开头的元素,实际上是调用 remove(0)。
def remove_first(self):
return self.remove(0)
# 返回指定索引 index 处的元素。
def get(self, index):
self._check_element_index(index)
return self.data[index]
# 将指定索引 index 处的元素设置为 element,并返回原始值。
def set(self, index, element):
self._check_element_index(index)
old_val = self.data[index]
self.data[index] = element
return old_val
# 返回列表的大小。
def size(self):
return self.size
# 返回列表是否为空。
def is_empty(self):
return self.size == 0
# 将列表的容量调整为 new_cap。
# 如果新容量小于当前大小,则不进行调整。
def _resize(self, new_cap):
if self.size > new_cap:
return
temp = [None] * new_cap
temp[:self.size] = self.data[:self.size]
self.data = temp
# 用于检查索引是否在有效范围内。
def _is_element_index(self, index):
return 0 <= index < self.size
def _is_position_index(self, index):
return 0 <= index <= self.size
# 用于检查索引是否在有效范围内,如果不在有效范围内,则抛出 IndexError。
def _check_element_index(self, index):
if not self._is_element_index(index):
raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))
def _check_position_index(self, index):
if not self._is_position_index(index):
raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))
# 使 MyArrayList 对象可迭代,从而可以使用 for 循环遍历其中的元素。
def __iter__(self):
self.p = 0
return self
def __next__(self):
if self.p == self.size:
raise StopIteration
self.p += 1
return self.data[self.p - 1]
# 打印
def display(self):
print(f"size = {self.size} cap = {len(self.data)}")
print(self.data)
if __name__ == "__main__":
arr = MyArrayList(3)
for i in range(1, 6):
arr.add_last(i)
arr.remove(3)
arr.add(1, 9)
arr.add_first(100)
val = arr.remove_last()
for i in range(arr.size):
print(arr.get(i))
print(arr.display())
双链表
from selenium.common import NoSuchElementException
class MyLinkedList:
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
def __init__(self):
self.head = self.Node(None)
self.tail = self.Node(None)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def add_last(self, e):
x = self.Node(e)
temp = self.tail.prev
temp.next = x
x.prev = temp
x.next = self.tail
self.tail.prev = x
self.size += 1
def add_first(self, e):
x = self.Node(e)
temp = self.head.next
temp.prev = x
x.next = temp
self.head.next = x
x.prev = self.head
self.size += 1
def add(self, index, element):
self._check_position_index(index)
if index == self.size:
self.add_last(element)
return
p = self._get_node(index)
temp = p.prev
x = self.Node(element)
p.prev = x
temp.next = x
x.prev = temp
x.next = p
self.size += 1
def remove_first(self):
if self.size < 1:
raise NoSuchElementException()
x = self.head.next
temp = x.next
self.head.next = temp
temp.prev = self.head
x.prev = x.next = None
self.size -= 1
return x.val
def remove_last(self):
if self.size < 1:
raise NoSuchElementException()
x = self.tail.prev
temp = x.prev
temp.next = self.tail
self.tail.prev = temp
x.prev = x.next = None
self.size -= 1
return x.val
def remove(self, index):
self._check_element_index(index)
x = self._get_node(index)
prev = x.prev
next = x.next
prev.next = next
next.prev = prev
x.prev = x.next = None
self.size -= 1
return x.val
def get(self, index):
self._check_element_index(index)
p = self._get_node(index)
return p.val
def get_first(self):
if self.size < 1:
raise NoSuchElementException()
return self.head.next.val
def get_last(self):
if self.size < 1:
raise NoSuchElementException()
return self.tail.prev.val
def set(self, index, val):
self._check_element_index(index)
p = self._get_node(index)
old_val = p.val
p.val = val
return old_val
def size(self):
return self.size
def is_empty(self):
return self.size == 0
def _get_node(self, index):
self._check_element_index(index)
p = self.head.next
for _ in range(index):
p = p.next
return p
def _is_element_index(self, index):
return 0 <= index < self.size
def _is_position_index(self, index):
return 0 <= index <= self.size
def _check_element_index(self, index):
if not self._is_element_index(index):
raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))
def _check_position_index(self, index):
if not self._is_position_index(index):
raise IndexError("Index: " + str(index) + ", Size: " + str(self.size))
def display(self):
print("size =", self.size)
p = self.head.next
while p != self.tail:
print(p.val, "-> ", end="")
p = p.next
print("null")
print()
def __iter__(self):
self.p = self.head.next
return self
def __next__(self):
if self.p == self.tail:
raise StopIteration
val = self.p.val
self.p = self.p.next
return val
if __name__ == "__main__":
# 创建一个 MyLinkedList 实例
linked_list = MyLinkedList()
# 在链表末尾添加元素
linked_list.add_last(1)
linked_list.add_last(2)
linked_list.add_last(3)
# 在链表开头添加元素
linked_list.add_first(0)
# 在指定位置插入元素
linked_list.add(2, 1.5)
# 输出链表大小
print("Size of linked list:", linked_list.size)
# 输出链表中的元素
print("Linked list elements:")
for val in linked_list:
print(val)
# 移除链表开头和末尾的元素
print("Removed first element:", linked_list.remove_first())
print("Removed last element:", linked_list.remove_last())
# 输出链表中的元素
print("Linked list elements after removal:")
for val in linked_list:
print(val)
🍋总结
下一节,我把单链表的也给出来,顺便做两道题应用一下以上的基本操作
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)