Python单链表原理与实现方法详解

2024-07-30 16:31:31

本文实例讲述了Python单链表原理与实现方法。分享给大家供大家参考，具体如下：

Python实现单链表

关于链表

链表（Linked List）是由许多相同数据类型的数据项按照特定顺序排列而成的线性表。
链表中个数据项在计算机内存中的位置是不连续且随机的，数组在内存中是连续的。
链表数据的插入和删除很方便，但查找数据效率低下，不能像数组一样随机读取数据。

单链表的实现

一个单向链表的节点由数据字段和指针组成，指针指向下一个元素所在内存地址
定义一个链表节点类,self.value实例属性表示节点数据字段；self.next表示指针；初始化值为None

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

在单链表中第一个节点为头(head)指针节点(即头指针指向的节点为单链表第一个节点，后续简称头指针节点)，从头指针节点出发可以遍历整个链表，进行元素查找，插入和删除，非常重要。一般不移动head头指针。
单链表中最后一个节点为尾节点，其指针为None，表示结束。
建立单链表我们首先需要创建头指针节点（引入头指针是为了方便操作单链表，对于头指针节点，只有指针域指向链表第一个节点，不含实际值）

class linkedList(object):
  def __init__(self):
    self.head = Node()	# 创建头指针结点
    self.length = 0	# 初始链表长度，头指针节点不计入长度
  def __len__(self):	# 重写特殊方法返回self.length
    return self.length

链表初始化之后，开始定义链表方法
链表头部插入节点：
- 调用Node()传入待插入的值value创建待插入节点
- 判断当前链表是否为空链表，链表为空：
  - 插入节点既是链表头指针指向的节点也是尾节点(指向None)
- 链表不为空：
  - 待插入节点指向原头指针节点，头指针重新指向待插入节点
  - 首先需要将原头指针结点，存放到临时变量中(防止head指针变更时，指针断裂导致数据丢失，链表中指针就是连接的纽带，其中某个纽带断裂(即指针指向其他)则后续数据都将丢失)
  - 将头指针指向新插入节点
  - 新插入节点指针指向原头指针节点
  - 长度+1
- ```
  def head_insert(self, value): # 链表头部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指针域指向原head元素
      tmp_head = self.head.next # 原头指针节点存储到tmp_head
      self.head.next = node # 新head指针指向node
      node.next = tmp_head # 新插入节点指向原头指针节点
    self.length += 1
```
链表头部删除节点：
- 依旧是先判断链表是否为空，为空则返回False
- 链表不为空时：
  - 头指针指针域(指针域存放下一节点的内存地址，即头指针节点)指向头指针，也就是说链表第一个节点变成了头指针head，由于head不计入链表，所以就相当于删除了第一个节点(有点绕)
  - 同时返回删除的值
- ```
  def head_del(self): # 删除头结点,返回头结点的值
    if self.head.next == None:
      return False
    else:
      # 头指针指针域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value
```

链表尾部添加节点：

创建待插入节点对象
判断链表是否为空，为空则头指针节点就是待插入节点，也是尾节点
链表不为空：
- 首先通过while循环(循环条件为节点指针是否为None)找到当前链表的最后一个元素
- 然后将当前最后一个元素指向待插入节点
- 长度+1

  def append(self, value):  # 链表尾部添加结点
    # 创建新插入的结点对象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一个节点，指针指向自己
    else:
      curnode = self.head.next  # 变量curnode存放指针
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 当为最后一个节点时，指针指向新插入节点
    self.length += 1

指定位置后面插入节点：
- 这里方法接受两个位置参数，index插入位置和value插入值
- 依旧创建新节点对象
- 判断是否为空
- 在链表不为空的条件下：
  - 首先定义一个变量表示当前节点，以及一个index索引比较数i
  - 使用while循环，索引比较数i != index时，更新当前节点
  - 找到索引位置节点后，首先让插入节点指向索引位置节点的下一个节点
  - 然后让索引位置节点指向插入节点
  - 链表长度+1
- ```
def insert(self, index, value):
	node = Node(value)
  if self.length == 0:
    self.head.next = node
  else:
    i = 0
    cur_node = self.head.next
    while i != index:
      cur_node = cur_node.next
      i += 1
    node.next = cur_node.next
    cur_node.next = node
  self.length += 1
```

给定值删除该值节点：

删除链表中给定的值我们需要遍历整个链表，因此需要创建一个可迭代对象
定义节点迭代方法

def iter_node(self):
  cur_node = self.head.next	#当前节点
  while cur_node.next != None:	# 对除最后一个节点进行可迭代化处理
    yield cur_node
    cur_node = curnode.next
  if cur_node.next == None:	# 对尾节点进行可迭代化处理
    yield cur_node

重写特殊方法–iter–，用来声明这个类是一个迭代器

def __iter__(self): # 遍历列表节点
  for node in self.iter_node():
     yield node.value

首先定义一个Flag变量(默认为False)，用来表示删除状态
依旧判断链表是否为空
链表不为空时：
- 设置一个前驱节点(当找到需要删除的节点时，先让前驱节点指向删除节点的后继节点)
- for循环遍历链表
  - 找到符合条件的值就让前驱节点指向，删除节点的后继节点，然后del删除node，Flag更改为True
  - 没找到符合条件的值，就更新前驱节点，继续遍历

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置节点为头结点
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置节点的值
      return Flag

完整代码：

# 定义链表节点类
class Node(object):
  def __init__(self, value=None, next=None):
    self.value = value # 节点元素
    self.next = next  # 指针

# 单链表类
class LinkedList(object):
  def __init__(self):
    self.head = Node() # 创建头结点
    self.length = 0 # 初始化链表长度

  def __len__(self):
    return self.length

  def __iter__(self): # 遍历列表节点
    for node in self.iter_node():
      yield node.value

  def iter_node(self):
    curnode = self.head.next
    while curnode.next != None:
      yield curnode
      curnode = curnode.next
    if curnode.next == None:
      yield curnode

  def head_insert(self, value): # 链表头部插入
    node = Node(value)
    if self.head.next == None:
      self.head.next = node
      node.next = None
    else:
      # 插入元素指针域指向原head元素
      tmp_head = self.head.next # 原头指针节点存储到tmp_head
      self.head.next = node # 新head指针指向node
      node.next = tmp_head # 新插入节点指向原头指针节点
    self.length += 1

  def head_del(self): # 删除头结点,返回头结点的值
    if self.head.next == None:
      return False
    else:
      # 头指针指针域指向自己
      self.head = self.head.next
      self.length -= 1
      return self.head.value

  def append(self, value):  # 链表尾部添加结点
    # 创建新插入的结点对象
    node = Node(value)
    if self.length == 0:
      self.head.next = node  # 只有一个节点，指针指向自己
    else:
      curnode = self.head.next  # 变量curnode存放指针
      while curnode.next != None:
        curnode = curnode.next
      curnode.next = node # 当为最后一个节点时，指针指向新插入节点
    self.length += 1

  # 这里的insert是指定值后面插入不是指定位置
  def insert(self, index, value):
    node = Node(value)
    if self.length == 0:
      self.head.next = node
      self.length += 1
    else:
      for nd in self.iter_node():
        if nd.value == index:  # 如果nd节点值等于index，则插入到nd后
          tmp_node = nd.next # 将nd的指针存放到中间变量
          nd.next = node # nd节点指向插入节点
          node.next = tmp_node  # 插入节点指向原nd.next节点
          self.length += 1
          return True
      return False

  def replace(self, old_value, new_value):
    index = 0
    if self.length == 0:
      return False
    else:
      for node in self.iter_node():
        if node == old_value:
          node.value = new_value
          index += 1
    if index != 0:
      return index # 替换节点数量(存在节点值相同情况)
    else:
      return False  # 替换失败，未找到替换值

  def delete_node(self, value):
    Flag = False
    if self.length == 0:
      return False
    else:
      previous_node = self.head  # 初始化前置节点为头结点
      for node in self.iter_node():
        if node.value == value:
          previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
          del node
          self.length -= 1
          Flag = True
        else:
          previous_node = node  # 更新前置节点的值
      return Flag

# 测试
l = LinkedList()
l.append(1)
l.append(2)
l.append(7)
l.append(5)
l.append(6)
l.append(7)
l.head_insert(3)
print("当前链表长度：%s" %l.length)
#print("删除头结点为：%d"% l.head_del())
print("当前链表长度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
  print("第%d个链表节点的值: %d"%(i, node))
  i += 1

运行结果：

当前链表长度：7
当前链表长度：7
第1个链表节点的值: 3
第2个链表节点的值: 1
第3个链表节点的值: 2
第4个链表节点的值: 7
第5个链表节点的值: 5
第6个链表节点的值: 6
第7个链表节点的值: 7

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

Python双向循环链表实现方法分析

本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针用于指
python双向链表实现实例代码

示意图: python双向链表实现代码: 复制代码代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(object): def __init__(self): self.he
Python编程实现双链表，栈，队列及二叉树的方法示例

本文实例讲述了Python编程实现双链表,栈,队列及二叉树的方法.分享给大家供大家参考,具体如下: 1.双链表 class Node(object): def __init__(self, value=None): self._prev = None self.data = value self._next = None def __str__(self): return "Node(%s)"%self.data class DoubleLinkedList(object): def
Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.
Python二叉搜索树与双向链表转换算法示例

本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s
Python数据结构之双向链表的定义与使用方法示例

本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje
Python单向链表和双向链表原理与用法实例详解

本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下
python双向链表原理与实现方法详解

本文实例讲述了python双向链表原理与实现方法.分享给大家供大家参考,具体如下: 双向链表一种更复杂的链表是"双向链表"或"双面链表".每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值:而另一个指向下一个节点,当此节点为最后一个节点时,指向空值. 操作 is_empty() 链表是否为空 length() 链表长度 travel() 遍历链表 add(item) 链表头部添加 append(item) 链表尾部添加 insert(pos,
Python双链表原理与实现方法详解

本文实例讲述了Python双链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现双链表文章目录 Python实现双链表单链表与双链表比较双链表的实现定义链表节点初始化双链表判断链表是否为空双链表尾部添加元素双链表头部添加节点: 双链表表头删除双链表按位置插入双链表删除指定节点完整代码单链表与双链表比较双链表比单链表多一个前驱指针位置,空间效率不占优势由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法) 双链表的实现定
python如何实现单链表的反转

这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

Python单链表原理与实现方法详解

Python实现单链表

关于链表

单链表的实现

相关推荐

随机推荐