【数据结构】数组、双链表代码实现

这篇具有很好参考价值的文章主要介绍了【数据结构】数组、双链表代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

🍋总结

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

【数据结构】数组、双链表代码实现,数据结构,数据结构,python

挑战与创造都是很痛苦的,但是很充实。文章来源地址https://www.toymoban.com/news/detail-826929.html

到了这里,关于【数据结构】数组、双链表代码实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(122)
  • Java 数据结构篇-实现双链表的核心API

    🔥博客主页:  小扳_-CSDN博客 ❤感谢大家点赞👍收藏⭐评论✍       文章目录         1.0 双链表的说明         1.1 双链表 - 创建         1.2 双链表 - 根据索引查找节点         1.3 双链表 - 根据索引插入节点         1.4 双链表 - 头插节点         1.5 双链表 - 尾插

    2024年02月04日
    浏览(55)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(58)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(200)
  • 数据结构与算法—一维数组、二维数组、矩阵、顺序串、链接串的C++代码实现

    1、一维数组:ArrayOneD.h 数组这种数据结构可以看作线性表的推广。数组一般采用顺序存储的方法表示。 这是一个模板类 ArrayOneD 的实现,用于表示一维数组。它包括了 构造函数、拷贝构造函数、析构函数、重载下标运算符、重载赋值运算符、求数组长度、重新设置数组长度

    2024年02月07日
    浏览(60)
  • C语言数据结构+KMP算法next数组优化计算方法+优化后子串匹配代码实现

    通过我之前那篇KMP算法的讲解,我们可以快速手算KMP算法的next数组,但是之前计算的next数组在一些情况下会有缺陷,比如模式串’aaaab’和主串’aaabaaaab’进行匹配 令模式串指针为j 当第一个元素不匹配时,下一次匹配还是要从模式串的第一个元素与主串匹配,其实我们可以直接写

    2024年02月06日
    浏览(48)
  • 数据结构--双链表

    单链表 VS 双链表 单链表:无法逆向检索,有时候不太方便 双链表:可进可退,存储密度更低一丢丢 在p结点之后插入s结点 特殊处理:p是最后一个结点 用后插操作实现结点的插入有什么好处? 按位序插入前插操作: 找到前一个结点进行后插操作 ####删除p的后继结点q 特殊处

    2024年02月11日
    浏览(38)
  • 【数据结构】双链表

     带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。 1.准备工作  由于实际开发项目中,项目的实现都是采用模

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包