[数据结构]总结---链表

1.今天总结一下链表这种数据结构

链表是一种很简单的数据结构，但是很实用。在区块链中，所有的链都是以链的方式相互连接的。
简单的说，单链表包括两个部分，第一个部分包括自己的信息，第二部分指向下一个节点的指针。

单链表.png

2.简单介绍一下操作

2.1 节点的信息，value保存信息，next指向下一个节点。

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

2.2 初始化，新建一个根节点，并设置最大长度，将链表长度和尾节点初始化

 # 初始化
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self.root = Node()
        self.tail_node = None
        self.length = 0

2.3 从末尾添加一个节点（要注意的地方就是判断链表本身是否为空，然后直接从tailnode节点添加）

 # 从右侧增加一个节点
    def append(self, value):
        if self.maxsize is not None and len(self) >= self.maxsize:
            raise Exception('LinkedList is Full')
        # 新建节点
        node = Node(value)
        tail_node = self.tail_node
        # 更新上一节点next(之前的尾节点)
        if tail_node is None:  # 如果末尾是空的
            self.root.next = node
        else:  # 加到最后
            tail_node.next = node
        # 更新尾节点
        self.tail_node = node
        self.length += 1

2.4 从左侧添加一个节点，还是需要判断尾节点tailnode是否为空

  # 从左边增加一个节点
    def append_left(self, value):
        if self.maxsize is not None and len(self) >= self.maxsize:
            raise Exception('LinkedList is Full')
        node = Node(value)
        # 如果是空的话，直接将node
        if self.tail_node is None:
            self.tail_node = node
        # 不是空，更换root指向的值
        head_node = self.root.next
        self.root.next = node
        node.next = head_node
        self.length += 1

2.5 在某一“value”后插入一节点。

 def insert(self, value, new_value):
        '''
        在某一值后插入新的值
        :param value: 旧值
        :param new_value: 需插入的新值
        '''
        for node in self.iter_node():
            if node.value is value:
                # 必须每次插入时，新建一个new_node
                new_node = Node(new_value)
                new_next = node.next
                # 当到最后一个时，必须更新tail_node
                if node.next is None:
                    self.tail_node = new_node
                node.next = new_node
                new_node.next = new_next

2.6 从尾删除节点

    def pop(self):
        # 获取长度
        length = self.length
        # 当空
        if length is 0:
            raise Exception("The LinkList is empty")
        # 当仅一个节点时
        elif length is 1:
            self.root.next = None
            self.length = 0
            self.tail_node = None
        # 大于两个节点时候
        length -= 1
        index = 1
        head_node = self.root.next
        # 找到节点
        while index is not length:
            length += 1
            head_node = head_node.next
        # 删除节点
        del head_node.next
        self.tail_node = head_node

2.7 从开头处删除节点

    def popleft(self):
        # 判断链表是否为空
        if self.root.next is None:
            raise Exception("The LinkList is empty")
        # 获取后一节点next值
        head_node = self.root.next
        self.root.next = head_node.next
        self.length -= 1
        value = head_node.value
        # 判断是否为唯一节点，处理尾部
        if self.tail_node is head_node:
            self.tail_node = None
        del head_node
        return value

3.完整代码

查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/1-List/Linklist.py