一、数组模拟单链表、邻接表

• 需要声明的变量：

  • head：存放头结点的下标

  • 节点的元素：e[N]、ne[N]

    e[N]存放值，ne[N]存放下标

class single_list():
    def __init__(self,N):
        self.head = -1 # 存放头结点指针
        self.e = [0] * N # 存放值
        self.ne = [0] * N # 存放next指针
        self.idx = 0 # 存放当前数组可以存放的位置，也是数量的表现

    def add_to_head(self,x):
        self.e[self.idx] = x
        self.ne[self.idx] = self.head
        self.head = self.idx
        self.idx += 1

    def add(self, k, x): # 在下标为k的点后面插入节点
        self.e[self.idx] = x
        self.ne[self.idx] = self.ne[k]
        self.ne[k] = self.idx
        self.idx += 1

    def remove(self, k): # 将下标为k的点后面的点删掉
        self.ne[k] = self.ne[self.ne[k]]

l = single_list(100)
l.add_to_head(1)
l.add_to_head(2)
i = l.head
while i != -1:
    print(l.e[i])
    i = l.ne[i]

二、数组模拟双链表（优化某些问题）

• 需要声明的变量

  • 头结点head和尾结点tail
    • 0表示左端点，1表示右端点
    • 即左端点右端点占据数组前两个元素
  • 节点的元素
    • e[N]：存放值
    • l[N]：指向左节点
    • r[N]：指向右节点

• 代码实现

  class double_list():
      def __init__(self,N):
          self.e = [0] * N # 存放值
          self.l = [0] * N # 存放左节点指针
          self.r = [0] * N # 存放右节点指针
          # 下标为0表示头结点，下标为尾结点
          self.r[0] = 1 # 头结点的右节点是尾结点
          self.l[1] = 0 # 尾结点的左节点是头结点
          self.idx = 2 # 存放当前数组可以存放的位置，头两个存放头尾节点了
  
      def add_to_head(self,x):
          self.e[self.idx] = x
          self.ne[self.idx] = self.head
          self.head = self.idx
          self.idx += 1
  
      def add(self, k, x): # 在下标为k的点后面插入节点
          # 先处理插入点的指向
          self.e[self.idx] = x
          self.r[self.idx] = self.r[k]
          self.l[self.idx] = k
          self.l[self.r[k]] = self.idx
          self.r[k] = self.idx
          self.idx += 1
  
      def remove(self, k): # 将下标为k的点后面的点删掉
          self.r[self.l[k]] = self.r[k] # k左边的右节点指向k的右节点
          self.l[self.r[k]] = self.l[k]
  

  • 注意点：
    • 下标为k的点表示第k-1个插入的点
    • 如果想在下标为k的点的前面插入点，只需add(l[k],x)