了解数据结构中的单向链表和双向链表

链表定义：将元素存放在通过连接构造起来的一系列存储块中

一、单链表

定义：每个节点两部分，即元素区elem和链接区next（指向下一个节点的地址）

• 第一个节点叫头结点

• 最后一个节点叫尾结点

• 尾结点的链接区指向空

# 创建一个节点类
class Node():
    def __init__(self, elem, next=None):
        self.elem = elem
        self.next = next


# 创建一个单链表类
class SingleLinkList():
    def __init__(self, node=None):
        # 定义私有属性头结点
        self.__head = node

    def is_empty(self):
        # 判断列表是否为空,只有头结点指向None则为空
        return self.__head == None

    def travel(self):
        # 遍历整个链表
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print()

    def length(self):
        # 链表长度，需要遍历，只要找到尾节点
        cur = self.__head  # cur游标，用来移动遍历节点,表示当前节点
        count = 0  # 负责计数
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def add(self, elem):
        # 头部添加元素，头插法
        first = self.__head
        node = Node(elem, next=first)
        self.__head = node

    def append(self, elem):
        # 尾部添加元素,尾插法
        node = Node(elem)
        cur = self.__head
        if self.is_empty():
            self.__head = node
        else:
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, elem):
        # 指定位置插入元素
        if pos  self.length() - 1:
            # 尾插法
            self.append(elem)
        else:
            pre = self.__head
            count = 0
            while count