文档章节

Python 链表(linked list)

o
 osc_wws45aot
发布于 2019/08/20 13:41
字数 617
阅读 0
收藏 0

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

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

优点

由于不必须按顺序存储,链表在插入、删除的时候可以达到O(1)的复杂度,比线性表快得多

缺点

相比于线性表顺序结构操作复杂,查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)

分类

单向链表

单向链表的链接方向是单向的,对链表的访问要从头部开始顺序读取

组成

每个结点包括两个部分: 是存储数据元素的数据域, 存储下一个结点地址的指针域

示例:

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

操作

  • 遍历
  • 插入、删除
  • 建立
    • 头插法
    • 尾插法
class Node(object):
    def __init__(self, item=None):
        self.item = item
        self.next = None


def traversal(head_node):
    """链表的遍历"""
    cur_node = head_node
    while cur_node is not None:
        print(cur_node.item)
        cur_node = cur_node.next


def add(value, cur_node):
    """链表的插入,在当前节点之后插入新的节点"""
    new_node = Node(value)
    new_node.next, cur_node.next = cur_node.next, new_node


def delete(cur_node):
    """链表的删除,删除当前节点之后的节点"""
    tar_node = cur_node.next
    cur_node.next = cur_node.next.next
    del tar_node


def create_linklist_f(li):
    """头插法建立链表"""
    head = Node()
    for num in li:
        temp = Node(num)
        temp.next, head.next = head.next, temp
    return head


def create_linklist_r(li):
    """尾插法建立链表"""
    head = Node()
    r_node = head
    for num in li:
        temp = Node(num)
        r_node.next, temp.next = temp, None
        r_node = r_node.next
    return head

双向链表

双向链表每个数据结点中都有两个指针,分别指向直接后继和直接前驱,所以从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点

组成

每个结点包括两个部分: 是存储数据元素的数据域, 存储下一个结点地址的指针域

示例:

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

循环链表

表中最后一个结点的指针域指向头结点,整个链表形成一个环

组成

每个结点包括两个部分: 是存储数据元素的数据域, 存储下一个结点地址的指针域

示例:

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

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
[LeetCode] 206. Reverse Linked List 反向链表

Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both? 反向链表,分别用递归和迭代方式实现。 递归Iteration......

osc_cddopi4y
2018/03/05
2
0
Leetcode【86、92、148、206】

问题描述:【Linked List】86. Partition List 解题思路: 这道题是给一个链表和整数 x,将小于 x 的数按位置顺序放在链表左侧,大于等于 x 的按位置顺序放在右侧。 类似于快排的划分过程有木...

牛奶芝麻
2019/10/28
0
0
Leetcode【61、82、83、142、143、1171】

问题描述:【Linked List】61. Rotate List 解题思路: 这道题是给一个链表,旋转链表,将链表每个结点向右移动 k 个位置。 1、先计算链表长度 size,,如果 ,则不用移动,直接返回 head; ...

牛奶芝麻
2019/10/28
0
0
Leetcode【24、109、328、455、725】

问题描述:【Linked List、Recursion】24. Swap Nodes in Pairs 解题思路: 这道题是给一个链表,相邻结点数值两两进行交换,要求不修改结点值且只能操作链表本身。 方法1:三指针完成交换 ...

牛奶芝麻
2019/10/28
0
0
[LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项

Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2Output: 1->2 Example 2: Input: 1->1->2->3->3Output: 1->2->3 移......

osc_2cpecyp0
2018/03/14
4
0

没有更多内容

加载失败,请刷新页面

加载更多

如果你失明了,你怎么编程? - How can you program if you're blind?

问题: Sight is one of the senses most programmers take for granted. 视觉是大多数程序员认为理所当然的感官之一。 Most programmers would spend hours looking at a computer monitor......

技术盛宴
49分钟前
16
0
如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
今天
11
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
今天
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部