线性数据结构（linear data structure）第四讲链表（linked list）

链表：有顺序关系的一组元素[1]。

链表的操作：

  • LinkedList() 创建一个新链表，返回空的链表。
  • add(item) 将item添加到链表头部，返回None。
  • append(item) 将item添加到链表尾部，返回None。
  • insert(pos, item) 在pos位置添加元素item，返回None。
  • remove(item) 从链表中删除第一个item元素，返回被删除的元素。
  • pop(pos) 从链表中删除pos位置上的元素，返回被删除的元素。pos默认为链表最后的位置。
  • index(item) 返回item在链表中的索引。没有找到时返回-1。
  • is_empty() 判断链表是否为空，返回True或者False。
  • size() 返回链表中元素个数。

链表的实现[2]：

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

class LinkedList:
    def __init__(self):
        self.head = None
    def add(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
    def append(self, item):
        current = self.head
        pre = None
        while current != None:
            pre = current
            current = current.next
        node = Node(item)
        if pre == None:
            self.head = node
        else:
            pre.next = node
    def index(self, item):
        current = self.head
        count = 0
        while current != None:
            if current.value == item:
                return count
            current = current.next
            count += 1
        return -1
    def is_empty(self):
        return self.head == None
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.next
        return count

链表的优点：

  • 在链表头部和尾部的操作快，适合实现堆和队列。

链表的缺点：

  • 查找速度慢，需要遍历[3]。

参考资料：

注[1]: 其实我也不知道怎么描述。链表还有有序链表，链表中的元素按照大小顺序排列；双向链表，链表中的每个节点可以有前后两个节点。

注[2]: 实际如果使用到，我想我应该想直接用Python的list。

注[3]: 如果是有序链表，在查找时可以使用二分查找加快查找速度，但是同样的在向有序链表中添加数据时相比较普通链表会花费更多时间。