链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

• 优点: 真正的动态 不需要处理容量的问题
  
• 缺点：不能随机访问

  链表实现

  ```python class Node: def init(self,value,next=None) -> None:

    self._value = value 
    self._next = next 

class LinkedList: def init(self) -> None:

    # 虚拟头结点 
    self.__dummyhead = Node(value=None,next=None) 
    self.__size = 0 
# 获取链表长度 
def get_size(self):
    return self.__size 
# 判断链表是否为空 
def is_empty(self):
    return self.__size == 0 
#  链表头部添加元素 
def add_first(self,value):
    # # 创建新节点 
    # node = Node(value=value)
    # # 当前节点的next执行之前的head节点 
    # node.__next = self.__head
    # # 改变head的指向
    # self.__head = node
    # self.__head = Node(value=value,next=self.__head)
    # self.__size +=1 
    self.add(0,value)
def add(self,index:int,value):
    assert index>=0 and index<=self.__size, " index error"
    node_prev = self.__dummyhead
    for i in range(self.__size):
        node_prev = node_prev._next
    # node_prev_next = node_prev.__next 
    # node = Node(value=value)
    # node_prev.__next = node 
    # node.__next = node_prev_next
    node_prev._next = Node(value=value,next=node_prev._next)
    self.__size +=1
# 尾部添加元素 
def addLast(self,value):
    self.add(self.__size,value)
# 获取链表元素 
def get(self,index):
    cur = self.__dummyhead._next 
    for i in range(index):
        cur = cur._next 
    return cur._value 
# 获取链表第一个元素 
def get_first(self):
    return self.get(0)
#  获取链表末尾元素 
def get_last(self):
    return self.get(self.__size -1 )
#  修改下标为index的值为 value
def set(self,index,value):
    cur = self.__dummyhead._next
    for i in range(index):
        cur = cur._next 
    cur._value = value 
# 查看链表中是否存在某个元素 
def contains(self,value) ->bool:
    cur = self.__dummyhead._next  
    while (cur is not None):
        if cur._value == value:
            return True
        else:
            cur = cur._next 
    return False 
#  删除指定位置的元素 
def remove(self,index):
    assert index>=0 and index<self.__size ," index error"
    cur = self.__dummyhead 
    for i in range(index):
        cur = cur._next 
    del_node = cur._next 
    cur._next = del_node._next 
    del_node.next = None 
    self.__size -=1 
    return del_node 
#  删除链表头元素 
def remove_first(self):
    return self.remove(0)
# 删除链表尾元素 
def remove_last(self):
    return self.remove(self.__size -1 )
def __str__(self) -> str:
    strs = "dummyhead -> "
    cur = self.__dummyhead._next 
    while (cur is not None):
        strs += f"{cur._value} -> "
        cur = cur._next 
    return strs + "None"

<a name="GP2yv"></a>
## 时间复杂度分析
- 添加 ：<br />add_first O(1)<br />add_last O(n)<br />add_index (n/2) O(n)<br />
- 删除 ：<br />remove_first O(1)<br />remove_last O(n)<br />remove_index (n/2) O(n)
- 查找 修改 O(n)
<a name="VFjBB"></a>
## 链表实现栈
用链表实现栈，可以理解为始终在链表头部添加元素（入栈）和在头部删除元素（出栈），这样在实现后其入栈和出栈操作的时间复杂度都为O(1)
```python
import abc
class Stack(metaclass=abc.ABCMeta):
    @abc.abstractmethod
    def pop(self):
        pass
    @abc.abstractmethod
    def push(self, item):
        pass
    @abc.abstractmethod
    def clear(self):
        pass
    @abc.abstractmethod
    def empty(self):
        pass
    @abc.abstractmethod
    def size(self):
        pass
    @abc.abstractmethod
    def top(self):
        pass
    @abc.abstractmethod
    def show(self):
        pass
class LinkedListStack(Stack):
    def __init__(self):
        self.__data = LinkedList()
    def push(self, item):
        """ 入栈 """
        self.__data.add_first(item)
    def empty(self):
        """ 判断是否为空栈 """
        return self.__data.is_empty()
    def size(self):
        """ 输出栈的大小 """
        return self.__data.get_size() 
    def pop(self):
        """ 出栈 """
        assert self.size() > 0, "stack is empty"
        return self.__data.remove_first()
    def top(self):
        """ 查看栈顶值 """
        assert self.size() > 0, "stack size is 0"
        return self.__data.get_first()
    def clear(self):
        """ 清空栈 """
        del self.__data 
    def show(self):
        str_start = "top ["
        node = self.__data.dummyhead.next
        for i in range(self.__data.get_size()):
            if i == self.__data.get_size() - 1:
                str_start += str(node.value)
            else:
                str_start += str(node.value) + ","
            node = node.next
        str_start += "]"
        print(str_start)

链表实现队列

在链表基础上实现队列其入队操作可以在链表头部进行操作，因为在链表头部删除一个元素的时间复杂度时O(1),在引入尾节点后对其在尾节点的添加操作时间复杂度可以优化到O(1)。因为队列基本的操作就是入队和出队两个操作。所以使用上处队列（使用链表实现）时间复杂度可以优化到O(1)。

"""
链表实现队列
"""
class Node:
    def __init__(self, value, next=None) -> None:
        self._value = value
        self._next = next
class LinkedListQueue:
    """
    使用链表实现队列 - 链表尾部进行入队操作 链表头部实现出队操作
    """
    def __init__(self) -> None:
        # 虚拟头结点
        self.__head = None
        self.__size = 0
        self.__tail = None
    # 获取链表长度
    def get_size(self):
        return self.__size
    # 判断链表是否为空
    def is_empty(self):
        return self.__size == 0
    def enqueue(self, value):
        # tail指向尾节点
        if self.__tail is None:
            self.__tail = Node(value=value)
            self.__head = self.__tail
        else:
            self.__tail._next = Node(value=value)
            self.__tail = self.__tail._next
        self.__size += 1
    def dequeue(self) -> Node:
        # 出队操作
        assert self.is_empty(), " queue is empty"
        ret_node = self.__head
        self.__head = self.__head._next
        ret_node._next = None
        if self.__head is None:
            self.__tail = None
        self.__size -= 1
        return ret_node
    def get_front(self):
        assert self.is_empty(), " queue is empty"
        return self.__head
    def __str__(self):
        str_s = "Queue front"
        node = self.__head
        for i in range(self.get_size()):
            str_s +=f" <- {node._value} "
            node = node._next
        str_s +=" None <- tail"
        return str_s