专栏首页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客来了(ltdo11),作者:bofeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打牢地基-队列

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

    用户1081422
  • 数据结构-数组

    工作了一段时间后,发现基础实在是太重要了,老话说: 万丈高楼平地起。地基不牢,肯定跑不快,天花板也愈发明显。

    用户1081422
  • 打牢地基-栈篇

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

    用户1081422
  • Python自建logging模块

    每一个logger对象,都有一个日志级别,它只会输出高于它level的日志。如果一个logger的level是INFO,那么调用logger.debug()是无...

    小破孩的梦想空间
  • 数据结构学习-python实现-优先队列--0417

    到不了的都叫做远方
  • 【CV中的Attention机制】BiSeNet中的FFM模块与ARM模块

    语义分割需要丰富的空间信息和相关大的感受野,目前很多语义分割方法为了达到实时推理的速度选择牺牲空间分辨率,这可能会导致比较差的模型表现。

    BBuf
  • Django打造大型企业官网(六)

    zhang_derek
  • 反运算(简单的定制)[第十七章]

    关于反运算,这里要注意一点;对于a + b,b的__radd__(self,other),中other是a的对象,self才是b的对象

    天钧
  • Python系列之循环定时器

    近期在学习并使用Python开发一些小工具,在这里记录方便回忆,也与各位开始走上这条路的朋友共勉,如有不正确希望指正,谢谢!

    py3study
  • 节约时间,珍惜生命,手写一个验证码图片标注程序

    做验证码图片的识别,不论是使用传统的ORC技术,还是使用统计机器学习或者是使用深度学习神经网络,都少不了从网络上采集大量相关的验证码图片做数据集样本来进行训练。

    州的先生

扫码关注云+社区

领取腾讯云代金券