文档章节

Python链表的实现与使用(单向链表与双向链表)

o
 osc_y8yehimr
发布于 2019/03/20 16:22
字数 894
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

参考【易百教程】用Python实现链表及其功能

  1 """
  2 python链表的基本操作:节点、链表、增删改查
  3 """
  4 import sys
  5 
  6 class Node(object):
  7     """
  8     节点类,实例化后的对象用来表示链表中的一个节点
  9     """
 10     def __init__(self, dataval=None):
 11         self.dataval = dataval
 12         self.nextval = None
 13 
 14 
 15 class SLinkedList(object):
 16     """
 17     链表类,用于初始化一个链表,及多链表的一些操作
 18     """
 19     def __init__(self):
 20         self.headval = None
 21 
 22     def listprint(self):
 23         """
 24         打印链表
 25         """
 26         val = self.headval
 27         while val is not None:
 28             print(val.dataval, end=' ')
 29             val = val.nextval
 30         print()
 31 
 32     def insertStart(self, newdata):
 33         """
 34         从链表头插入一个节点
 35         param@newdata: 插入的新节点,为Node类实例对象的dataval
 36         """
 37         newdata = Node(newdata)
 38         newdata.nextval = self.headval
 39         self.headval = newdata
 40 
 41     def insertEnd(self, newdata):
 42         """
 43         从链表尾部插入一个节点
 44         param@newdata: 插入的新节点,为Node类实例对象的dataval
 45         """
 46         newdata = Node(newdata)
 47         if self.headval == None:
 48             self.headval = newdata
 49             return
 50         else:
 51             temp = self.headval
 52             while temp.nextval:
 53                 temp = temp.nextval
 54             temp.nextval = newdata
 55 
 56     def insertBetween(self, node, newdata):
 57         """
 58         在链表的node节点后插入一个新元素
 59         param@node: 链表中的一个节点,新插入的元素将插入其后面
 60         param@newdata: 插入的新节点,为Node类实例对象的dataval
 61         """
 62         if (not node) or node == None:
 63             raise Exception('参数异常!')
 64         else:
 65             newdata = Node(newdata)
 66             newdata.nextval = node.nextval
 67             node.nextval = newdata
 68 
 69     def removeNode(self, node_val):
 70         """
 71         从链表中删除值为node_val的节点
 72         param@node_val: 被删除节点的值,即Node类实例对象的dataval
 73         """
 74         if self.headval == None:
 75             print('链表为空链表!')
 76         else:
 77             if self.headval.nextval == None:
 78                 if self.headval == node_val:
 79                     sefl.headval = None
 80                 else:
 81                     return
 82             else:
 83                 temp = self.headval
 84                 if temp.dataval == node_val:
 85                     self.headval = temp.nextval
 86                 else:
 87                     temp = self.headval
 88                     while temp.nextval:
 89                         if temp.nextval.dataval == node_val:
 90                             temp.nextval = temp.nextval.nextval
 91                             break
 92                         temp = temp.nextval
 93 
 94 
 95 
 96 
 97 
 98 li = SLinkedList()
 99 e1 = Node('one')
100 e2 = Node('two')
101 e3 = Node('three')
102 li.headval = e1 
103 e1.nextval = e2 
104 e2.nextval = e3 
105 li.listprint()

 以上为单向链表一些基本操作的Python实现,接下来也展示一下双向链表的一些简单实现

 1 """
 2 双向链表
 3 """
 4 import sys
 5 import collections
 6 
 7 # 双向链表的节点类
 8 class Node(object):
 9     def __init__(self, data):
10         self.data = data
11         self.next = None
12         self.prev = None
13 
14 
15 # 双向链表类
16 class DoubleLinkedList(object):
17     def __init__(self):
18         self.head = None
19 
20     def push(self, newdata):
21         """
22         尾插法插入数据,也就是向链表的结尾追加元素
23         param@newdata: 新插入的数据,为Node类的实例对象的data
24         """
25         newdata = Node(newdata)
26         if self.head == None:
27             self.head = newdata
28         elif self.head.next == None:
29             newdata.next = self.head.next
30             self.head.next = newdata
31             newdata.prev = self.head
32         else:
33             data = self.head
34             while data.next:
35                 data = data.next
36             newdata.next = data.next
37             data.next = newdata
38             newdata.prev = data
39             
40     # 正向打印出链表值的函数
41     def listprint(self):
42         data = self.head
43         while data is not None:
44             print(data.data, end=' ')
45             data = data.next
46         print()
47 
48     # # 反向打印出链表值的函数
49     def listprint_2(self):
50         data = self.head
51         while data.next:
52             data = data.next
53         while data is not None:
54             print(data.data, end=' ')
55             data = data.prev
56         print()
57 
58     def insert(self, prev_node, newdata):
59         """
60         在链表的一个节点后插入一个节点
61         param@prev_node: 要插入节点的前一个节点
62         param@newdata: 插入的节点的值,为Node类实例对象的data
63         """
64         newdata = Node(newdata)
65         if prev_node is None:
66             return
67         elif prev_node.next is None:
68             newdata.next = prev_node.next
69             prev_node.next = newdata
70             newdata.prev = prev_node
71         else:
72             prev_node.next.prev = newdata
73             newdata.prev = prev_node
74             newdata.next = prev_node.next
75             prev_node.next = newdata
76         
77 
78 
79 dlist = DoubleLinkedList()
80 dlist.push('one')
81 dlist.push('two')
82 dlist.push('three')
83 dlist.insert(dlist.head, 'hhh')
84 dlist.listprint()
85 dlist.listprint_2()

暂时到这里

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
链表,栈与队列

链表 因为顺序表的要求是存储数据的内存是连续的,所以一旦原本内存不够的情况下就需要动态的改变数据区; 现在我们想要实现有一种数据结构,在扩充的时候,原有的数据不需要变,每多一个数据...

osc_fjmtyahf
2019/11/04
2
0
python链表

一 简介 1 链表简介 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可...

长跑者1号
2019/07/24
0
0
单链表的python实现

  首先说下线性表,线性表是一种最基本,最简单的数据结构,通俗点讲就是一维的存储数据的结构。   线性表分为顺序表和链接表: 顺序表示指的是用一组地址连续的存储单元依次存储线性表的...

osc_ve0sxjnb
2018/06/13
3
0
数据结构——动手实战双向链表

点击上方蓝字,和我一起学技术。 本文分享自微信公众号 - TechFlow(techflow2019)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起...

承志Y
03/04
0
0
数据结构——动手实战双向链表

本文始发于个人公众号:TechFlow,原创不易,求个关注 <br> 在之前介绍SkipList的文章当中,有一些同学反馈说由于对链表缺少认知以及了解,所以直接啃算法有些过于困难。加上之前的文章当中介...

osc_04fmvbv4
04/16
1
0

没有更多内容

加载失败,请刷新页面

加载更多

63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
21分钟前
26
0
前后端分离了,跨域问题怎么处理?

利用Nginx反向代理解决跨域问题 使用jsonp 来进行解决,不推荐,老项目可以使用此方案,但是发送的http 请求体有大小限制,并且发送方式为get方式,大小限制、不安全。 服务器代理 CORS 请求...

SpringForA
23分钟前
19
0
Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 00:00 How to track and display profile views on GitHub - (rushter.com) 如何在GitHub上跟踪和显示概要视图 得分:80 | 评论:36 XMEMS Announces World's First Mon......

FalconChen
37分钟前
83
0
如何在Java中将文本追加到现有文件 - How to append text to an existing file in Java

问题: I need to append text repeatedly to an existing file in Java. 我需要将文本重复添加到Java中的现有文件中。 How do I do that? 我怎么做? 解决方案: 参考一: https://stackoom...

fyin1314
昨天
12
0
Eclipse HotKey:如何在选项卡之间切换? - Eclipse HotKey: how to switch between tabs?

问题: How can I switch between opened windows in Eclipse? 如何在Eclipse中打开的窗口之间切换? There is Ctrl + F6 , but it's asking me which one I want, but I want switch it lik......

富含淀粉
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部