python版本单链表实现代码
作者:冬日新雨 发布时间:2022-12-06 16:49:26
今天看了一下数据结构的书,发现其实数据结构没有几种,线性表,数组,字符串,队列和栈,等等,其实是一回事,然后就是树结构,图结构。数据结构的理论并不难,主要是要自己写一下这些数据结构以及对应的基本的操作方法,这样就能够更快的提高。
这一篇blog写一下线性表。
线性表:分为顺序表和链表
一、顺序表
顺序表就是相对于表中的数据,地址也是顺序的,所以可以随机存取。但是在操作插入和删除元素的时候,由于要满足地址的连续性,所以要移动很多的元素位置,因此,插入或者删除一个顺序表的元素的时间复杂度是o(n)。很多时候,在对顺序表做合并的时候,需要先对表中的元素进行排序,然后再进行处理,这样可以避免每次都从头进行查询。
二、链表
链表就失去了顺序表的随机存取特点,即每次从中取一个元素都要从头开始找,这样耗费了一些时间,时间复杂度为o(n);但是在做插入和删除,以及两个链表合并的时候,就方便了很多,只需要做一点指针修改就可以了。
链表中的每一个元素节点都包含了数据部分和下一个节点的指针。一般在链表的头部附设一个头结点,而且头结点一般不存储数据,而是存放一些长度等附加信息,或者不存储。
在很多语言中没有指针这一概念,而有数组的概念,比如java和python,java中的数组还要求定义数组的类型,也就是说必须都是同一类型的数据,而python则没有要求,所以python的list更贴近链表的真正含义。这种用数组描述的链表叫做静态链表。使用静态链表来描述链表对此类语言要方便很多了,本身这些语言都提供了内置类来处理链表。
除此之外,还有循环链表,双向链表(解决了无法向前搜索的问题,但是在修改指针的时候需要有更多的操作)。
# -*- coding=utf-8 -*-
# 这个例子是Python版本的单链表
class Node(object):
def __init__(self, value, next=0):
self.value = value
self.next = next # 指针
class LinkedList(object):
# 链表的数据结构
def __init__(self):
self.head = 0 # 头部
def __getitem__(self, key):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.get_elem(key)
def __setitem__(self, key, value):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.set_elem(key, value)
def init_list(self, data): # 按列表给出 data
self.head = Node(data[0])
p = self.head # 指针指向头结点
print p, self.head
for i in data[1:]:
p.next = Node(i) # 确定指针指向下一个结点
p = p.next # 指针滑动向下一个位置
print self.head.next.next
def get_length(self):
length = 0
p = self.head
while p != 0: # 0 值就是Node结点中默认的 0 值,表示下一个结点没有了,即没有为其赋值
length += 1
p = p.next
return length
def is_empty(self):
if self.head == 0:
return True
else:
return False
def insert_node(self, index, value):
if index < 0 or index > self.get_length():
print 'Can not insert node into the linked list.'
elif index == 0:
temp = self.head
self.head = Node(value, temp)
else:
p, post = self.head, self.head
for i in xrange(index):
post = p
p = p.next
temp = p
post.next = Node(value, temp)
def delete_node(self, index):
if index < 0 or index > self.get_length()-1:
print "Wrong index number to delete any node."
elif self.is_empty():
print "No node can be deleted."
elif index == 0:
temp = self.head
self.head = temp.next
elif index == self.get_length():
p = self.head
for i in xrange(self.get_length()-2):
p = p.next
p.next = 0
else:
p = self.head
for i in xrange(index-1):
p = p.next
p.next = p.next.next
def show_linked_list(self): # 打印链表中的所有元素
if self.is_empty():
print 'This is an empty linked list.'
else:
p, container = self.head, []
for _ in xrange(self.get_length()-1):
container.append(p.value)
p = p.next
container.append(p.value)
print container
def clear_linked_list(self): # 将链表置空
self.head = 0
def get_elem(self, index):
if self.is_empty():
print "The linked list is empty. Can not get element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to get any element."
else:
p = self.head
for _ in xrange(index):
p = p.next
return p.value
def set_elem(self, index, value):
if self.is_empty():
print "The linked list is empty. Can not set element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to set element."
else:
p = self.head
for _ in xrange(index):
p = p.next
p.value = value
def get_index(self, value):
p = self.head
for i in xrange(self.get_length()):
if p.value == value:
return i
else:
p = p.next
return -1
l = LinkedList()
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.init_list([1, 5, 12, "fjd", 45, 999])
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.insert_node(4, 100)
l.insert_node(6, "cecil")
l.show_linked_list()
print "The value of index 0 is: ", l.get_elem(0)
l.set_elem(0,1000)
l.show_linked_list()
print "the index of *** is: ", l.get_index(1009)
print "The length of linked list now is: ", l.get_length()
l.delete_node(3)
#l.clear_linked_list()
l.show_linked_list()
来源:https://blog.csdn.net/dongrixinyu/article/details/78618971
猜你喜欢
- 代码如下:Dim strName, iLoop For Each strName 
- 钉钉设置机器人首先在钉钉设置钉钉机器人群设置—> 智能群助手—>添加机器人—>自定义添加完成,得到一个Webhook AP
- 在之前的一篇文章我们介绍了《如何向PHP数组中头部和尾部添加元素》既然有添加元素,那么就有删除元素,今天这篇文章详细介绍如何删除数组中的头部
- * 惯,请先看测试页面:event-test.html 结论:在非IE浏览器,同一元素同一事件类型的处理函数是先进先出的。只有IE下,是先进
- 一、首先我们来填个坑支付验签失败这个问题折磨了我两天,官方文档比较含糊不清。各种百度下来的方法试过之后也不尽人意,最后发现问题是没有二次签名
- 这篇文章主要介绍了Python读取表格类型文件代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 有时一些网页对源码进行了加密,我们很难找到类似像“onselectstart="return false"”这样的代码,
- 一、需求描述web 自动化测试/python爬虫往往会遇到扫码登录的情况,不是所有的网站都支持用户密码登录,遇到这种扫码登录的情况会阻碍我们
- 我有个需求就是抓取一些简单的书籍信息存储到mysql数据库,例如,封面图片,书名,类型,作者,简历,出版社,语种。我比较之后,决定在亚马逊来
- 相关代码如下: 1. 创建sequence: 代码如下:CREATE SEQUENCE SEQU_DATA_DATAINFO IN
- px比em更加容易使用,em指字体高,任意浏览器的默认字体高都是16px。所以未经调整的浏览器都符合: 1em=16px,所以10px=0.
- 本文实例讲述了Python求导数的方法。分享给大家供大家参考。具体实现方法如下:def func(coeff): sum=
- 最近在为公司做一个门户网站,项目并不咋D,可规划却不小.在做的过程中就发现修改占了很大的工作量.于是就开始想了想如何使前端修改轻松一些.这个
- Monster是Alipay UED推出的网站代码分析、质量检测及评分的浏览器扩展,它能智能分析CSS、JS、HTML内容并生动形象展示网页
- 本文较为详细的讲述了PHP图片库imagemagick的安装方法。分享给大家供大家参考。具体方法如下:1.下载ImageMagickhttp
- txt文件转换为XML很多目标检测的模型都是默认需要VOC的文件输入格式手上数据label是txt文件。为了避免不必要的bug,还是选择转换
- 1、jsp前端<%-- Created by IntelliJ IDEA. User: Lenovo Date: 2020/6/19
- 本文实例讲述了PHP模板引擎Smarty中变量的使用方法。分享给大家供大家参考,具体如下:一、概述:Smarty 是 PHP 众多模板引擎中
- 在 Go 语言中,struct 是一种常见的数据类型,它可以用来表示复杂的数据结构。在 struct 中,我们可以定义多个字段,每个字段可以
- 今天萌发一个想法,用css来实现透视效果。起初,我想到的是我们常见的添加阴影效果的方法,用多个div通过偏移来实现,但这需要很多 div,不