Python Linked List 链表 数据结构

发布于 2022-01-31 13:09:29 字数 3660 浏览 1095 评论 0

单向链表:

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) 时间复杂度

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据

关于作者

JSmiles

生命进入颠沛而奔忙的本质状态,并将以不断告别和相遇的陈旧方式继续下去。

0 文章
0 评论
84961 人气
更多

推荐作者

醉城メ夜风

文章 0 评论 0

远昼

文章 0 评论 0

平生欢

文章 0 评论 0

微凉

文章 0 评论 0

Honwey

文章 0 评论 0

qq_ikhFfg

文章 0 评论 0

    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文