Python Linked List 链表 数据结构

Question

单向链表:

class listNode:    # 链表中的结点
  def __init__(self, x):
    self.val = x
    self.next = None

class LinkedList:    # 链表类
  def __init__(self):
    self.head = None

l1 = LinkedList()
l1.add(1)
l1.add(2)

size() —— 返回链表中数据元素的个数/链表长度

def size(self):
  size = 0
  head = self.head
  while head:
    size += 1
    head = head.next
  return size

empty() —— 若链表为空则返回一个布尔值 true

def empty(self):
  return True if self.head else False

value_at(index) —— 返回第 n 个元素的值（从0开始计算），若索引超过链表长度则报错

def value_at(self, index):
  if not self.head:
    raise IndexError("Index out of range.")
  head = self.head
  while index > 0:
    if not head:
      raise IndexError("Index out of range.")
    head = head.next
    index -= 1
  return head.val

add(value) —— 添加元素到链表的首部

def add(self, value):
  new_node = listNode(value)
  new_node.next = self.head
  self.head = new_node

pop_front() —— 删除首部元素并返回其值，若链表为空则报错

def pop_front(self):
  if not self.head:
    raise IndexError("Pop from empty list")
  value = self.head.val
  self.head = self.head.next
  return value

append(value) —— 添加元素到链表的尾部

def append(self, value):
  new_node = listNode(value)
  if not self.head:
    self.head = new_node
    return
  head = self.head
  while head.next:
    head = head.next
  head.next = new_node

pop_back() —— 删除尾部元素并返回其值，若链表为空则报错

def pop_back(self):
  if not self.head:
    raise IndexError("Pop from empty list")
  if not self.head.next:
    value = self.head.val
    self.head = None
    return value
  head = self.head
  while head.next.next:
      head = head.next
  value = head.next.val
  head.next = None
  return value

front() —— 返回首部元素的值，若链表为空则报错

def front(self):
  if not self.head:
    raise ValueError("Linked list is empty")
  return self.head.val

back() —— 返回尾部元素的值，若链表为空则报错

def back(self):
  if not self.head:
    raise ValueError("Linked list is empty")
  head = self.head
  while head.next:
      head = head.next
  return head.val

insert(index, value) —— 插入值到指定的索引，若索引超出链表长度则报错

def insert(self, index, value):
  if not self.head:
    raise IndexError("Index out of range")
  head = self.head
  new_node = listNode(value)
  if index == 0:
    new_node.next = head
    self.head = new_node
    return
  while index - 1 > 0:
    head = head.next
    if not head:
      raise IndexError("Index out of range")
    index -= 1
  temp = head.next
  head.next = new_node
  new_node.next = temp

erase(index) —— 删除指定索引的节点，若索引超出链表长度则报错

def erase(self, index):
  if not self.head:
    raise IndexError("Index out of range")
  head = self.head
  if index == 0:
    self.head = head.next
  while index - 1 > 0:
    index -= 1
    head = head.next
    if not head:
      raise IndexError("Index out of range")
  temp = head.next
  head.next = temp.next

reverse() —— 逆序链表

def reverse(self):
  prev = None
  head = self.head
  while head:
    temp = head.next
    head.next = prev
    prev = head
    head = temp
  self.head = prev

remove(value) —— 删除链表中指定值的第一个元素

def remove(self,value):
  if not self.head:
    return
  head = self.head
  if head.val == value:
    self.head = head.next
    return
  while head.next:
    if head.next.val == value:
      temp = head.next.next
      head.next = temp
      return
    head = head.next

时间复杂度：

• 在链表的首部插入/移除结点、获得链表首部的值，都是 O(1) 时间复杂度
• 获取/移除/插入任一结点、尾部结点，都是 O(n) 时间复杂度