单链表

在闭关刷了几天的leetcode后,我发现了一个事情,就是海贼王真好看,单刷leecode太无聊了,于是乎我边刷题边看海贼王,也是这就是我效率很低的原因,刷了一些题后也相应的去看一下别人说的如何刷才是有效率的,所以现在来记录一下关于链表的实现。


链表是什么:

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。-------摘自百度百科

通俗的讲,链表不像list或者数组那样,但是却能实现那样的功能。

为什么用链表?

如果我们用list的话,要在中间插入一个数字,比如在[1,3]中插入一个2,只需要把3换成2,再添加3,如果很长的list呢,很复杂了,但是用链表的话,就很简单了,把前一个指向到要插入的,再插入的这个指向之前的下一个。

创建链表第一步初始化结点类:

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

然后再初始化链表类:

class listnode:
    def __init__(self):
        self.head =0
    def is_empty(self):
        return self.head == 0         #判断这个链表是不是空链表
    def initlist(self, data):     #初始化链表,并传入节点数据
        self.head = Node(data[0])
        p = self.head         #这里的p是一个Node类型的数据,用for传入数据和指针域
        for i in data[1:]:
            node = Node(i)
            p.next = node
            p = p.next

然后再添加一些增删改查的函数,就算是创建完成一个简单的链表了。

从后面增加一个数据:

    def append(self, item):
        q = Node(item)
        if self.head == 0:
            self.head = q
        else:
            p = self.head
            while p.next != None:
                p = p.next
            p.next = q

查看链表的长度:

def getlen(self):
    p = self.head
    len = 0
    while p != 0:
        len+=1
        if p.next == None:
            break
        else:
            p = p.next
    return len

删除链表某个数据:

def delete(self,index):
    if self.is_empty() or index<0 or index>self.getlen():
        print('链表为空')
    else:
        if index == 0:
            self.head = self.head.next
        else:
            j = 0
            n = self.head
            p = self.head
            while n.next and j<index:
                p = n
                n = n.next
                j+=1
            if j == index:
                p.next = n.next

修改链表的数据:

def uadate(self,index,data):
    if self.is_empty() or index<0 or index>self.getlen():
        print('链表为空')
    else:
        p = self.head
        j = 0
        while p.next and j<index:
            p = p.next
            j+=1
        if j== index:
            p.val = data

查看链表某个的值:

def getitem(self, item):
    if self.is_empty():
        print('Linklist is empty.')
        return
    j = 0
    p = self.head
    while p.next != 0 and j < item:
        p = p.next
        j += 1
    if j == item:
        return p.val
    else:
        print  'target is not exist!'

遍历一遍链表的值:

def traver(self):
    if self.is_empty():
        print('链表为空')
    else:
        p = self.head
        while p.next:
            print(p.val)
            p = p.next

链表中插入数值:

def insert(self,index,data):
    if self.is_empty() or index<0 or index>self.getlen():
        print('链表为空')
    else:
        if index == 0:
            q = Node(data,self.head)
            self.head = q

        else:
            j = 0
            pst = self.head
            p = self.head
            while p.next and j<index:
                pst = p
                p = p.next
                j+=1
                if index == j:
                    q = Node(data)
                    pst.next = q
                    q.next = p

主要靠理解,其次靠理解,第三还是要靠理解。

本文分享自微信公众号 - 孤独的S(sjw_980305)

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

原始发表时间:2019-08-16

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

DLM:微信大规模分布式n-gram语言模型系统

Wechat & NUS《A Distributed System for Large-scale n-gram Language Models at Tenc...

14720
来自专栏AI科技大本营的专栏

拯救CPU

导语:在过去的10-20年间,硬件技术取得了惊人的进步,但在高性能数据中心和高度受限的移动环境中却仍然不能“奢求”廉价的性能。很多人认为,硬件的下一个进步是将神...

8820
来自专栏品茗IT

Java数据结构和算法

特点:我们都知道数组中的元素在内存中连续存储的,可以根据是下标快速访问元素,因此,查询速度很快,然而插入和删除时,需要对元素移动空间,比较慢。

11920
来自专栏品茗IT

SpringBoot入门建站全系列(五)使用Spring-data-jpa操作数据库CRUD

Mybatis插件:比较时髦,比较适合sql复杂,或者对性能要求高的应用,因为sql都是自己写的。

11830
来自专栏品茗IT

java集合及concurrent并发包

集合包最常用的有Collection和Map两个接口的实现类,Colleciton用于存放多个单对象,Map用于存放Key-Value形式的键值对。

11030
来自专栏品茗IT

git commit emoji 使用指南

git commit 时使用 emoji 为本次提交打上一个 “标签”, 使得此次 commit 的主要工作得以凸现,也能够使得其在整个提交历史中易于区分与查找...

9240
来自专栏机器学习算法与Python学习

【ML小白】10 个机器学习 Q&A,面试必知!

本文整理了一些最常见的机器学习面试问题及其相应的回答。机器学习有志者以及经验丰富的ML专业人员可以在面试前以此巩固其基础知识。

8530
来自专栏品茗IT

Spring序列化布尔类型错误

反例:定义为基本数据类型 Boolean isDeleted;的属性,它的方法也是isDeleted(),RPC框架在反向解析的时候,“以为”对应的属性名称是d...

10550
来自专栏品茗IT

Spring环境下使用Netty写Socket和Http详解

Netty是目前最流行的由JBOSS提供的一个Java开源框架NIO框架,Netty提供异步的、事件驱动的网络应用程序框架和工具,用以快速开发高性能、高可靠性的...

8210
来自专栏品茗IT

SpringBoot入门建站全系列(九)文件上传功能与下载方式

Spring对文件上传做了简单的封装,就是用MultipartFile这个对象去接收文件,当然有很多种写法,下面会一一介绍。

12140

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励