专栏首页T客来了打牢地基-链表

打牢地基-链表

章节

  • 动态数组 & 栈 & 队列 与 链表的不同
  • 链表特性 & 图示
  • 链表实现 & 各操作时间复杂度分析

动态数组 & 栈 & 队列 与 链表的不同

重要 动态数组、栈、队列 底层依托的都是静态数组 链表是天然的动态数据结构

链表重要性 & 简介 & 图示

重要性:

  1. 1. 真正的动态数据结构
  2. 2. 最简单的动态数据结构
  3. 3. 涉及更深入的引用(或者指针)
  4. 4. 更深入的理解递归 (天然具有递归属性,node.next is node )
  5. 5. 辅助组成其他数据结构 - 栈、队列也可以用链表实现,还有hashmap

链表 - LinkedList

  1. 1. 数据存储在节点中
  2. class Node {
  3. // 存储具体的数据
  4. E e;
  5. // 指向下一个node的引用
  6. Node next;
  7. }

链表数据结构如下图所示:

优点: 1.真正的动态,不需要处理固定容量问题 2.增删数据非常方便

缺点:

  1. 丧失了随机访问的缺点

链表实现 & 各操作时间复杂度分析

链表实现 - python 版

注意: 关键点: 找到要插入节点的前一个节点 LinkedList - (head实现)

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/5 下午3:44
 
# @Author  : bofengliu@tencent.com
 
# @Site    : 
 
# @File    : LinkedList.py
 
# @Software: PyCharm
 
# 自己实现链表元素需要的节点
 
# head 版
 
"""
  
class Node:
 
 def __init__(self, e=None, next=None):
 
        self.e = e
 
        self.next = next
 


 
 def to_string(self):
 
 return self.e
 

 
class LinkedList:
 
 """
 
    链表中的成员变量,head 指向链表中头节点,size 是链表中元素的个数
 
    """
 
 
 def __init__(self):
 
        self._head = None
 
        self._size = 0
 
 
 def get_size(self):
 
 return self._size
 

 def is_empty(self):
 
 return self._size == 0
 
 
 def add_first(self, val):
 
 """
 
        头插法
 
        :param node:
 
        :return:
 
        """
 
        node = Node(e=val)
 
        node.next = self._head
 
        self._head = node
 
 # 简写
 
 # self._head = Node(val, self._head)
 
        self._size += 1
 


 
 def add(self, index, e):
 
 if index < 0 or index > self._size:
 
 raise (Exception, 'Add failed! Illegal index')
 
 if index == 0:
 
 # 这步操作可以通过虚拟头节点屏蔽掉
 
            self.add_first(e)
 
 else:
 
            prev = self._head
 
 for i in range(0, index - 1):
 
                prev = prev.next
 
            new_node = Node(e=e)
 
            new_node.next = prev.next
 
            prev.next = new_node
 
 # 简写
 
            prev.next = Node(e, prev.next)
 
        self._size += 1
 


 
 def add_last(self, e):
 
        self.add(self._size, e)
 

LinkedList - (dummy_head 虚拟节点实现)

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 
""" 
# @Time    : 2020/2/5 下午3:44 
# @Author  : bofengliu@tencent.com 
# @Site    :  
# @File    : LinkedList.py 
# @Software: PyCharm 
# 自己实现链表元素需要的节点 
# dummy_head(虚拟头节点)版 
# 删除和新增都需要找到前一个节点 
""" 
class Node: 
 def __init__(self, e=None, next=None): 
        self.e = e 
        self.next = next 
 def to_string(self): 
 return self.e 
class LinkedList: 
 """ 
    链表中的成员变量,head 指向链表中头节点,size 是链表中元素的个数 
    """ 
 def __init__(self): 
        self._dummy_head = Node(None, None) 
        self._size = 0 
 def get_size(self): 
 return self._size 
 def is_empty(self): 
 return self._size == 0 
 def add(self, index, e): 
 """ 
        实质是占用原有index元素的位置,并将原有index元素向后移动 
        :param index: 
        :param e: 
        :return: 
        """ 
 if index < 0 or index > self._size: 
 raise (Exception, 'Add failed! Illegal index') 
        prev = self._dummy_head 
 for i in range(0, index): 
            prev = prev.next 
        new_node = Node(e=e) 
        new_node.next = prev.next 
        prev.next = new_node 
 # 简写 
 # prev.next = Node(e, prev.next) 
        self._size += 1 
 def add_first(self, e): 
 """ 
        头插法 
        :param e: 
        :return: 
        """ 
        self.add(0, e) 
 def add_last(self, e): 
        self.add(self._size, e) 
 def get(self, index): 
 if index < 0 or index > self._size: 
 raise (Exception, 'Get failed! Illegal index') 
 # 链表的真实头节点 
        cur = self._dummy_head.next 
 for i in range(0, index): 
            cur = cur.next 
 return cur.e 
 def get_first(self): 
 return self.get(0) 
 def get_last(self): 
 return self.get(self._size - 1) 
 # 更新操作 
 def set(self, index, e): 
 if index < 0 or index > self._size: 
 raise (Exception, 'set failed! Illegal index') 
        cur = self._dummy_head.next 
 for i in range(0, index): 
            cur = cur.next 
        cur.e = e 
 # 删除操作 
 def remove(self, index): 
 if index < 0 or index > self._size: 
 raise (Exception, 'set failed! Illegal index') 
        prev = self._dummy_head 
 for i in range(0, index): 
            prev = prev.next 
        del_node = prev.next 
        prev.next = del_node.next 
        del_node.next = None 
        self._size -= 1 
 return del_node.e 
 def remove_first(self): 
 return self.remove(0) 
 def remove_last(self): 
 return self.remove(self._size - 1) 
 # 查找链表中是否存在某个元素 
 def contains(self, e): 
        cur = self._dummy_head.next 
 while cur is not None: 
 if cur.e == e: 
 return True 
            cur = cur.next 
 return False 
 def to_string(self): 
        res_linkedlist_arr = [] 
        res_linkedlist_arr.append('LinkedList:size = %d  ' % self._size) 
        cur = self._dummy_head.next 
 while cur is not None: 
            val = cur.e 
 if isinstance(val, int): 
                val = str(val) 
            res_linkedlist_arr.append(val + ' -> ') 
            cur = cur.next 
        res_linkedlist_arr.append(' NULL ') 
 return "".join(res_linkedlist_arr) 
if __name__ == '__main__': 
    a = 1 
    linkedList = LinkedList() 
 for i in range(0, 5): 
        linkedList.add_first(i) 
 print(linkedList.to_string()) 
    linkedList.set(1, 2) 
 print(linkedList.to_string()) 
    linkedList.add(5, 10) 
 print(linkedList.to_string()) 
    linkedList.remove_first() 
 print(linkedList.to_string()) 
    linkedList.remove_last() 
 print(linkedList.to_string()) 
    linkedList.remove(1) 
 print(linkedList.to_string()
 

各操作时间复杂度分析

add 操作

add_last  O(n) 复杂度
 
add_first O(1) 复杂度
 
add(index, e) O(n/2) 即 O(n) 的复杂度
 

remove 操作

remove_last O(n)
 
remove_first O(1)
 
remove(index,e) O(n/2) 即 O(n) 的复杂度
 

set 操作

set(index,e)  O(n) 

get

get(index) O(n)
 
contains(e) O(n)

增删改查的时间复杂度都是O(n) 级别的,单对链表头节点(即虚拟头节点的下一个实体节点),时间复杂度是O(1)

文章分享自微信公众号:
T客来了

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

如有侵权,请联系 yunjia_community@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 打牢地基-队列

    数组队列 dequeue 的时间复杂度是 o(n) ,因每次删除队首元素,后面的元素都得进行前移操作 使用循环队列可以将dequeue的时间复杂度降至o(1)

    用户1081422
  • 打牢地基-栈篇

    底层实现并不关心, 栈通过动态array(capacity 可以动态变化)实现即可,栈的操作是array的子集

    用户1081422
  • 打牢地基-二叉树、BST

    二分搜索树-BTS 加速查询过程的原因,假如根节点val = 28, 现在在查找 30 这个元素,因为BTS的存储特性,只需要查找右子树部分就可以了,大大提高了...

    用户1081422
  • 打牢地基-拿下红黑树

    红黑树与2-3树的等价关系,理解2-3树和红黑树之间的关系 红黑树就很简单了 学习2-3树不仅对理解红黑树有帮助,对于理解B类树,也是有巨大帮助的:

    用户1081422
  • 打牢地基-映射的底层实现(LinkedListMap、BSTMap)

    注意:设置了 getnode 辅助函数, contains()、get()、set() 都会用的到

    用户1081422
  • 【编程基础】盖大楼地基要牢固

    水之积也不厚,则其负大舟也无力。——庄子 上一篇讲了几个编译编辑器,大家都可以用用,新手掌握几个是没有坏处的。 学编程要从基础学起,就像盖大楼,先把地基打好,...

    程序员互动联盟
  • 从0到1打牢算法基础之手写一个哈希表

    目的:手写实现一个哈希表,采用拉链法构建,每个hash(key)对应的是一个红黑树。

    公众号guangcity
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • Python打牢基础,从12个语法开始!

    Python简单易学,但又博大精深。许多人号称精通Python,却不会写Pythonic的代码,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pyth...

    小小詹同学
  • chrome打开本地链接

    同事之前给我提了一个需求,想实现在网页里点击链接地址后直接打开指定的地址(路径是内网共享的目录,file://share.xx.com\x\x)。

    meteoric
  • 大牛带你打牢Python基础,看看这10语法

    都说Python简单,易懂,但是有时候却又很深奥,许多人都觉的自己学会了,却老是写不出项目来,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pytho...

    一墨编程学习
  • 单链表就地转置

    试写一道算法,实现单链表的就地逆置(反转),即利用原表的存储空间将线性表(a1,a2,⋯an)逆置(反转)为(an⋯ ,a2,a1)。 输入格式

    小飞侠xp
  • 链表应用--基于链表实现栈

    在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳

    wfaceboss
  • 比特币的私钥【区块链生存训练】

    投资比特币,钱包和私钥是非常重要的两个概念,在这上面多花一些时间琢磨透是绝对值得的。千万别忙忙活活几个月,只因犯了一个低级错误,把买来的BTC拱手送人了。 我推...

    申龙斌
  • 从尾到头打印链表

    题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。 链表结点定义如下: struct ListNode { int m_nKey; ...

    猿人谷
  • 从尾到头打印链表

    用户3003813
  • [剑指offer] 从尾到头打印链表

    一种方法是利用栈来实现; 另外一种方法是利用三个指针把链表反转,关键是 r 指针保存断开的节点。

    尾尾部落

扫码关注云+社区

领取腾讯云代金券