数组与链表

layout: posttitle: 数据结构与算法—数组与链表
date: 2019-10-20
tag: 数据结构与算法

数组

• 下标索引从0 开始
• 存储的内存是连续的
• 常见的操作是增删查改
• 数组不能够越界（写程序的时候要注意边界条件）
• 数组读取元素和更新元素的时间复杂度都是 O(1)

• 插入数组存在三种操作

  • 尾部插入
  • 中间插入
  • 超范围插入（创建的新数组是原数组长度的两倍）
• 删除操作
• 数组的插入和删除操作的时间复杂度都是 O(n)
• 数据的适用场景：读操作多，写操作少

链表

• 链表（Linked list）是一种在物理上非连续、非顺序的数据结构，由若干个节点（node）组成
• 有单向链表和双向链表
• 单向链表的每个节点包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针 next
• 链表的第一个节点被称作头节点，最后一个节点被称作尾节点，尾节点的 next 指针指向空（Null）
• 链表在内存的存储方式是随机存储，可以灵活有效利用零散的碎片空间
• 链表的基本操作：增删查改
• 查找链表节点的时间复杂度是 O(n)

• 插入节点

  • 尾部插入
  • 头部插入
  • 中间插入

• 删除节点

  • 尾部插入
  • 头部插入
  • 中间插入
• 插入和删除节点的时间复杂度是 O(1)
• 链表的适用场景：需要在尾部频繁的插入、删除元素 | | 查找 | 更新 | 插入 | 删除 | | —- | —- | —- | —- | —- | | 数组 | O(1) | O(1) | O(n) | O(n) | | 链表 | O(n) | O(n) | O(1) | O(1) |

代码演示

数组程序 1

class MyArray:
    """
    通过 python 的列表封装成数组
    数组是没有负下标索引的
    """
    def __init__(self, capacity: int):
        self._data = []
        self._capacity = capacity
    def __getitem__(self, position: int) -> object:
        return self._data[position]
    def __setitem__(self, index: int, value: object):
        self._data[index] = value
    def __len__(self) -> int:
        return len(self._data)
    def __iter__(self):
        for item in self._data:
            yield item
    def find(self, index: int) -> object:
        try:
            return self._data[index]
        except IndexError:
            return None
    def delete(self, index: int) -> bool:
        try:
            self._data.pop(index)
            return True
        except IndexError:
            return False
    def insert(self, index: int, value: int) -> bool:
        if len(self) >= self._capacity:
            return False
        else:
            return self._data.insert(index, value)
    def print_all(self):
        for item in self:
            print(item)
def test_myarray():
    array = MyArray(5)
    array.insert(0, 3)
    array.insert(0, 4)
    array.insert(1, 5)
    array.insert(3, 9)  
    array.insert(3, 10)   
    assert array.insert(0, 100) is False # 插满以后不能再插入
    assert len(array) == 5
    assert array.find(1) == 5
    assert array.delete(4) is True
    print("array.find(6)", array.find(6)) # 索引超出范围
    array.print_all()
if __name__ == "__main__":
    test_myarray()

数组程序 2

class MyArray:
    """
    通过 python 的列表封装成数组
    数组是没有负下标索引的
    """
    def __init__(self, capacity: int):
        self._data = []
        self._capacity = capacity
    def __getitem__(self, position: int) -> object:
        return self._data[position]
    def __setitem__(self, index: int, value: object):
        self._data[index] = value
    def __len__(self) -> int:
        return len(self._data)
    def __iter__(self):
        for item in self._data:
            yield item
    def find(self, index: int) -> object:
        try:
            return self._data[index]
        except IndexError:
            return None
    def delete(self, index: int) -> bool:
        try:
            self._data.pop(index)
            return True
        except IndexError:
            return False     
    # 可以超范围插入
    def insert(self, index: int, value: int) -> bool:
        if len(self) >= self._capacity:
            self._capacity = 2*self._capacity # 扩容两倍
            return self._data.insert(index, value)
        else:
            return self._data.insert(index, value)
    def print_all(self):
        for item in self:
            print(item)
def test_myarray():
    array = MyArray(5)
    array.insert(0, 3)
    array.insert(0, 4)
    array.insert(1, 5)
    array.insert(3, 9)  
    array.insert(3, 10)   
    for i in range(6):
        array.insert(i, i)
    print("len(array)", len(array))  # 这样跟定义的数组长度冲突，容易引发歧义，不建议使用
    array.print_all()
if __name__ == "__main__":
    test_myarray()