算法与数据结构之链表

fansichao 2021-10-23 16:29:27

Categories： Tags：

链表

链表是计算机科学中最常用的数据结构之一。它也是最简单的结构之一，也是更高层结构(如堆栈、循环缓冲区和队列)的基础

定义
- 链表是计算机科学中最常用的数据结构之一。它也是最简单的结构之一，也是更高层结构(如堆栈、循环缓冲区和队列)的基础
- 列表是通过引用连接的单个数据元素的集合.数据元素可以由地址数据、地理数据、几何数据、路由信息或事务细节组成。通常，链接列表的每个元素都具有特定于列表的相同数据类型
- 单个列表元素称为节点。节点不同于顺序存储在内存中的数组。相反，它可能会在不同的内存段中找到它们，您可以通过跟踪从一个节点到下一个节点的指针找到这些内存段。通常使用 null 元素标记列表的结尾，该元素由 python 等效的 None 表示。
- 链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题
- 链表允许插入和删除表上任意位置上的节点，但是不允许随即存取
- 内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。
单链表数据结构
- head 保存首尾节点的地址
- data1,next -> data2,next -> data3,next
双链表数据结构
- head=None 时为首节点，next=null 时为尾节点
- head,data,next -> head,data,next -> head,data,next
链表类型
- 单链接列表
  - 节点只指向列表中的下一个元素
- 双链接列表
  - 节点指向列表中的下一个元素，也指向上一个节点
- 循环链表
  - 循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点
链表应用场景
- 数组应用场景：
  - 数据比较少
  - 经常做的运算是按序号访问数据元素；数组更容易实现，任何高级语言都支持；
  - 构建的线性表较稳定。
- 链表应用场景：
  - 对线性表的长度或者规模难以估计
  - 频繁做插入删除操作
  - 构建动态性比较强的线性表。

手把手实现 python 的链表数据结构

数组和链表差异分析

数组和链表的差异分析
- 差异点
  - 链表是链式的存储结构；数组是顺序的存储结构。
  - 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
  - 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；
  - 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
- 相同点
  - 两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

单链表和双链表的差异

一、方向不同
- 单链表只有指向下一个结点的指针
- 双链表既有指向下一个结点的指针，也有指向上一个结点的指针
二、适用情况不同
- 单向链表更适合元素的增加与删除
- 双向链表更适合元素的查询工作
三、读取不同
- 单链表只能单向读取
- 双链表可以双向读取

链表的代码实现

单链表 Python 代码实现

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)


# 通过单链表构建一个list的结构： 添加  删除  插入   查找 获取长度  判断是否为空...
# list1 = []  list1.append(5)     [5,]             slist =  SingleList()   slist.append(5)
class SingleList:
    def __init__(self, node=None):
        self._head = node

    def isEmpty(self):
        return self._head == None

    def append(self, item):
        # 尾部添加
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    # 求长度
    def len(self):
        cur = self._head
        count = 0

        while cur != None:
            count += 1
            cur = cur.next

        return count

    # 遍历
    def print_all(self):
        cur = self._head
        while cur != None:
            print(cur)
            cur = cur.next

    def pop(self, index):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if index == 0:
            self._head = self._head.next
        else:
            cur = self._head
            # 找到当前下标的前一个元素
            while index - 1:
                cur = cur.next
                index -= 1
            # 修改的next的指向位置
            cur.next = cur.next.next

    def insert(self, index, item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        if index == 0:
            node.next = self._head
            self._head = node
        else:
            cur = self._head

            while index - 1:
                cur = cur.next
                index -= 1

            node.next = cur.next
            cur.next = node

    def update(self, index, new_item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(new_item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(new_item)

        if index == 0:
            node.next = self._head.next
            self._head = node
        else:
            cur = self._head
            node.next = cur.next.next
            cur.next = node



    def remove(self, item):
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        cur = self._head
        while cur == node:
            cur = cur.next
        cur.next = cur.next.next


if __name__ == '__main__':
    slist = SingleList()
    print(slist.isEmpty())  # True
    print(slist.len())

    slist.append(5)
    print(slist.isEmpty())  # False
    print(slist.len())  # 1

    slist.append(8)
    slist.append(6)
    slist.append(3)
    slist.append(1)
    print(slist.isEmpty())  # True
    print(slist.len())
    print('---------------------')
    slist.print_all()

    print('----------pop-------------')
    slist.pop(2)
    slist.print_all()

    print('--------insert-------')
    slist.insert(1, 19)
    slist.print_all()

    print('--------update-------')
    slist.update(1, 18)
    slist.print_all()

    print('--------remove-------')
    slist.remove(18)
    slist.print_all()

双链表 Python 代码实现

'''
双向链表
'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

    def __str__(self):
        return str(self.data)


class DoubleList:
    def __init__(self):
        self._head = None

    def isEmpty(self):
        return self._head == None

    def append(self, item):
        # 尾部添加
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node

        # 求长度

    def add(self, item):
        node = Node(item)
        if self.isEmpty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node

    def len(self):
        cur = self._head
        count = 0

        while cur != None:
            count += 1
            cur = cur.next

        return count

    def print_all(self):
        cur = self._head
        while cur != None:
            print(cur)
            cur = cur.next

    def insert(self, index, item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        if index == 0:
            node.next = self._head
            node.prev = self._head.prev
            self._head = node
        else:
            cur = self._head

            while index - 1:
                cur = cur.next
                index -= 1

            node.next = cur.next
            node.prev = cur.prev
            cur.next = node
            cur.prev = node.prev

    def remove(self, item):
        if isinstance(item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(item)

        cur = self._head
        while cur == node:
            cur = cur.next

        cur.next = cur.next.next
        cur.prev = cur.prev

    def update(self, index, new_item):
        if index < 0 or index >= self.len():
            raise IndexError('index Error')
        if isinstance(new_item, Node):
            raise TypeError('不能是Node类型')
        else:
            node = Node(new_item)

        if index == 0:
            node.next = self._head.next
            node.prev = self._head.prev
            self._head = node
        else:
            cur = self._head
            node.next = cur.next.next
            node.prev = cur.prev
            cur.next = node
            cur.prev = node


if __name__ == '__main__':
    dlist = DoubleList()

    print(dlist.len())
    print(dlist.isEmpty())

    # dlist.append(6)
    # dlist.append(9)
    # dlist.append(5)
    # print(dlist.len())
    # print(dlist.isEmpty())
    # dlist.print_all()

    dlist.add(6)
    dlist.add(9)
    dlist.add(5)

    dlist.print_all()

    print('--------insert-------')
    dlist.insert(1, 19)
    dlist.print_all()

    print('--------update-------')
    dlist.update(1, 18)
    dlist.print_all()

    print('--------remove-------')
    dlist.remove(18)
    dlist.print_all()

单链表和双链表的 Python 代码实现

算法与数据结构之链表

链表

数组和链表差异分析

单链表和双链表的差异

链表的代码实现

相关资源