索取营销诊断书
021-80394720QQ
    您的位置：上海毫米网络优化公司 > 网站优化分享 >
    相关推荐recommended
    【数据结构】数组、双链表代码实现
    作者：mmseoamin日期：2024-03-04

    💗💗💗欢迎来到我的博客，你将找到有关如何使用技术解决问题的文章，也会找到某个技术的学习路线。无论你是何种职业，我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章，也欢迎在文章下方留下你的评论和反馈。我期待着与你分享知识、互相学习和建立一个积极的社区。谢谢你的光临，让我们一起踏上这个知识之旅！

    【数据结构】数组、双链表代码实现,请添加图片描述,第1张

    文章目录

    • 🍋数组（Array）
    • 🍋链表（Linked List）
    • 🍋代码实现
    • 🍋总结

      🍋数组（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)

      🍋总结

      下一节，我把单链表的也给出来，顺便做两道题应用一下以上的基本操作

      【数据结构】数组、双链表代码实现,请添加图片描述,第2张

      挑战与创造都是很痛苦的，但是很充实。

       

    上一篇：DS：八大排序之堆排序、冒泡排序、快速排序

    下一篇：算法沉淀——动态规划之简单多状态 dp 问题（上）（leetcode真题剖析）

    网站优化运营
    整站seo优化
    网络营销运营
    成功案例
    品牌创意网站
    营销型网站
    小程序
    微信小程序
    微信公众号
    百度熊掌号
    网站优化分享
    关于我们
    公司概况
    公司新闻
    公司文化
    结构体系
    企业资质
    加入我们
    关注我们
    扫描二维码
    获取更多信息
    精彩一手掌握
    Copyright © 2014-2019 seo,上海网站优化_网络制作_网站seo排名_网站建设推广_上海网络公司 版权所有 沪ICP备19022315号