单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置(python中的标识)
  • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

节点实现

class Node(object):
"""节点"""
def __init__(self, elem):
self.elem = elem
self.next = None

单链表的操作

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item) 链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • search(item) 查找节点是否存在

单链表的实现

class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.__head = node

单链表 判断链表是否为空(is_empty)

def is_empty(self):
"""链表是否为空"""
return self.__head == None

单链表 链表长度(length)

def length(self):
"""链表长度"""
# cur游标,用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count

单链表 遍历整个链表(travel)

def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")

单链表 链表尾部添加元素,尾插法(append)

def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node

单链表 链表头部插入元素,头插法(add)

def add(self, item):
"""链表头部添加元素,头插法"""
node = Node(item)
node.next = self.__head
self.__head = node

单链表 指定位置插入元素(insert)

 def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 当循环退出后,pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node

单链表 删除节点(remove)

def remove(self, item):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next

单链表 查找节点是否存在(search)

def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False

单链表 完整代码及测试

# coding:utf-8
class Node(object):
"""节点"""
def __init__(self, elem):
self.elem = elem
self.next = None class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.__head = node def is_empty(self):
"""链表是否为空"""
return self.__head == None def length(self):
"""链表长度"""
# cur游标,用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("") def add(self, item):
"""链表头部添加元素,头插法"""
node = Node(item)
node.next = self.__head
self.__head = node def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 当循环退出后,pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node def remove(self, item):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False if __name__ == "__main__":
ll = SingleLinkList()
print(ll.is_empty())
print(ll.length()) ll.append(1)
print(ll.is_empty())
print(ll.length()) ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
# 8 1 2 3 4 5 6
ll.insert(-1, 9) # 9 8 1 23456
ll.travel()
ll.insert(3, 100) # 9 8 1 100 2 3456
ll.travel()
ll.insert(10, 200) # 9 8 1 100 23456 200
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
"""
result:
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6
"""

链表与顺序表的对比

链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示:

操作链表顺序表
访问元素O(n)O(1)
在头部插入/删除O(1)O(n)
在尾部插入/删除O(n)O(1)
在中间插入/删除O(n)O(n)

注意虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。

Python实现单项链表的更多相关文章

  1. c++刷题(27/100)反转单项链表,链表的倒数第k个

    题目1:调整数组顺序使奇数位于偶数前面 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位 ...

  2. Python实现单链表数据的添加、删除、插入操作

    Python实现单链表数据的添加.删除.插入操作 链表的定义: 链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结 ...

  3. 关于c语言单项链表尾添加

    犹豫了几天,看了很多大牛写的关于c语言链表,感触很多,终于下定决心,把自己对于链表的理解随之附上,可用与否,自行裁夺.由于作者水平有限也是第一次写,不足之处,竭诚希望得到各位大神的批评指正.制作不易, ...

  4. 用python实现单向链表

    单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域ele ...

  5. python实现单链表反转(经典笔试题)

    https://blog.csdn.net/su_bao/article/details/81072849 0.说在前面的话 链表结构,说难不难,说易不易,一定要亲自编程实现一下.其次就是一定要耐心, ...

  6. python实现单链表的翻转

    #!/usr/bin/env python #coding = utf-8 class Node:     def __init__(self,data=None,next = None):      ...

  7. python数据结构之链表(一)

    数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟 ...

  8. 用Python写单向链表和双向链表

    链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表 ...

  9. python实现单链表的反转

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #!/usr/bin/env python #coding = utf-8 ...

  10. python描述:链表

    单链表结构: 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点 ...

随机推荐

  1. 20220925 - CSP-S 模拟赛 #2

    20220925 - CSP-S 模拟赛 #2 时间记录 \(8:00-8:20\) 浏览题面 \(8:20-8:45\) T1 想到了分块计算,但是在手推样例的过程中,发现样例的数据并不能真正构成一 ...

  2. 齐博x1如何录制阿里等第三方直播流

    暂时只支持windows录制,可以在你本地电脑进行录制体验.点击下面的网址,下载录制程序文件,直接解压到任何一个目录都可以.里边同时包含自建直播服务器的功能,不用自建直播流的话,就可以忽视相关配置即可 ...

  3. python django超链接

    之前用django框架打了一个简易的博客网站,现在说说怎么用django做超链接. 本文基于之前讲解的博客应用,如果只想学超链接请自行删减代码或评论提问. 首先,在templates文件夹下添加det ...

  4. eDP接口简介

    1. eDP背景介绍   随着显示分辨率的越来越高,传统的VGA.DVI等接口逐渐不能满足人们的视觉需求. 随后就产生了以HDMI.DisplayPort为代表的新型数字接口,外部接口方面HDMI占据 ...

  5. SQL---ltrim()和rtrim()函数的使用

    背景 去除字符串首尾空格大家肯定第一个想到trim()函数,不过在sqlserver中是没有这个函数的,却而代之的是ltrim()和rtrim()两个函数. 看到名字所有人都 知道做什么用的了,ltr ...

  6. 5 why 分析法,一种用于归纳抽象出解决方案的好方法

    最近在看了<微信背后的产品观 - 张小龙手抄版>,其中有段话如下: 用户需求是零散的,解决方案是归纳抽象的过程 那如何归纳抽象呢?是否有一定的实践方法论呢?经过一轮探讨和学习,有这些答案: ...

  7. PMM实现监控Mysql-MGR

    一.docker安装PMM服务端 1.安装yum配置单元 # 如果已安装,略过此步 yum install -y yum-utils #yum配置单元 2.配置docker阿里云yum源 #配置doc ...

  8. 我的Python基础(二)

    python包含6种内奸的序列:列表.元组.字符串.Unicode字符串.buffer对象和xrange对象 列表和元组的主要区别在于,列表可以修改,元组则不能. 索引: 使用负数索引时,最后一个元素 ...

  9. Crond服务+Shell实现秒级任务

    服务 [[email protected] ~]# chkconfig --list | grep crond crond 0:off 1:off 2:on 3:on 4:on 5:on 6:of ...

  10. 已经有 MESI 协议,为什么还需要 volatile 关键字?

    本文已收录到  GitHub · AndroidFamily,有 Android 进阶知识体系,欢迎 Star.技术和职场问题,请关注公众号 [彭旭锐] 进 Android 面试交流群. 前言 大家好 ...