初识链表 快来打我* 2022-05-25 09:19 172阅读 0赞 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 **链表的构建:** 构建内部类: private class Note{ public E e; public Note next; } 第一步:创建节点对象 Note first =new Note(); Note second=new second(); Note third =new Third(); 第二步:对数据e和对象的引用next赋值 first.e="a";//假设此时泛型E为字符串String类型 second.e="b"; third.e="c"; //将链表串联起来 first.next=second; second.next=third; third.next=null;//此时为最后一个元素,默认初始值为null ![链表的构建过程][70] **向链表中添加元素(表头、表中、表尾)** 1.向表头添加元素 主要思想:首先新建一个节点(Note)对象newNote,将first节点暂时赋给newNote,并将newNote的对象引用指向first,最后将fist赋值给newNote。实现代码如下: Note newNote=new Note(e); newNote.next=first; newNote=first; 2.向表中添加元素 主要思想:首相创建一个新的节点对象(newNote),获取到需要插入的对应位置的前一个节点prev和prev所指向的下一个节点对象prev.next,将newNote.next指向prev.next,prev.next指向newNote。代码实现如下: Note newNote=new Note(e); newNote.next=prev.next; prev.next=newNote; 3.向表尾添加元素 主要思想:同理创建一个新的节点对象newNote,将原先的最后一个节点third暂时赋给newNote,并将third.next指向newNote,最后将third赋值给newNote(这里third也可以改为last,表示链表的最后一个节点),代码实现如下: Note newNote=new Note(e); third.next=newNote; newNote=third; **链表具体底层实现如下:** public class LinkedList<E>{ private class Note{ public E e; public Note next; public Note(E e,Note next){ this.e=e; this.next=next; } public Note(E e){ this(e,null); } public Note(){ this(null,null); } public String toString(){ return e.toString; } } private Note heard; public int size; public LinkedList(){ heard=null; size=0; } public int getSize(){ return size; } public boolean isEmpty(){ return size==0;//或者note.next==null } //在表头添加元素 public void addFirst(E e){ Note note=new Note(e); note.next=heard; note=heard; size++ } //在链表的任意位置添加元素 public void add(int index,E e){ if(index<0||index>size){ throw new IllegalArgumentException("添加失败,不合法!"); } if(index==0){ addFirst(e); size++; } else{ Note prev=heard; for(int i=0;i<index-1;i++){ prev=prev.next; } Note note=new Note(e); note.next=prev.next; prev.next=note; size++; } } //在链表末尾添加元素 public addLast(E e){ add(size,e); size++; } } [70]: /images/20220525/1220e4f337c349f0b2d7d4869fa7b1f3.png
相关 单向链表·初识【c语言】 文章目录 顺序表和链表的优缺点 入门·增删改查【大佬请路过】 增 头插·思路·代码 尾插·思路·代码 ╰+攻爆jí腚メ/ 2024年04月06日 10:32/ 0 赞/ 81 阅读
相关 初识数据结构——顺序表 【数据结构】之顺序表(C语言版) 目录 【数据结构】之顺序表(C语言版) 1.线性表的定义 2.什么是顺序表 顺序表的定义 3. 曾经终败给现在/ 2023年09月28日 15:27/ 0 赞/ 21 阅读
相关 1.Mysql数据库——初识创建表 Mysql数据库——创建表 一、使用命令行创建表 ->>> 建表语句: create table 表名 ( 列名1 列类型【完整性约束】, 列名2 列类 女爷i/ 2023年06月18日 14:57/ 0 赞/ 17 阅读
相关 设计模式初识——责任链模式 一 概述 为了避免请求发送者与多个请求处理者耦合在一起,将所有请求的处理者通过前一对象记住其下一个对象的引用而连成一条链,当请求发生的时候,可将请求沿着这条链传递,知道有 旧城等待,/ 2022年12月13日 01:41/ 0 赞/ 176 阅读
相关 初识内核链表 前面我们说过如何用C实现通用类型的链表,比如void\的指针,零长数组等。可是小菜鸟毕竟赶不上大师,还是Linux内核巧妙啊,这里面的链表,才是链表中的“奇葩”。 今天药忘吃喽~/ 2022年08月24日 00:45/ 0 赞/ 179 阅读
相关 初识java 新的学期初识Java,在这一周的Java学习中学习到了两种排序的方法:冒泡法和选择法排序 首先说一下冒泡法 例如一组数据5 9 3 1 6从小到大排列 第一轮 骑猪看日落/ 2022年05月28日 04:55/ 0 赞/ 411 阅读
相关 初识链表 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 快来打我*/ 2022年05月25日 09:19/ 0 赞/ 173 阅读
相关 初识区块链 1.区块链概念: 区块链是由包含交易信息的区块从后向前有序链接起来的数据结构。 区块被从后向前有序地链接在这个链条里,每个区块都指向前一 桃扇骨/ 2022年05月21日 00:46/ 0 赞/ 172 阅读
相关 哈希表初识 转载自:[https://www.cnblogs.com/lchzls/p/6714079.html][https_www.cnblogs.com_lchzls_p_67140 骑猪看日落/ 2022年05月13日 04:28/ 0 赞/ 180 阅读
还没有评论,来说两句吧...