数据结构-线性表-模拟实现单链表

熵桥冰川
• 阅读 1000

单链表实现

创建节点类

public class Node {
    /**
     * 为了便于理解 不使用private修饰
     */
    Object data;//存储数据的引用
    Node next;//下一个节点的引用
public Node() {
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
 }

创建链表类

public class SingleLinkedList implements List {

    private Node head = new Node();//头节点,不存储数据,为了编程方便
    
    private int size;//一共有几个结点
    }

查找第i 个节点的值

在单链表中进行查找操作只能从链表的首节点开始,通过每个节点的next 引用来依次访问链表中的每个节点,以完成相应的查找操作

public Object get(int i) {
//如果i的位置错误报异常
        if (i<0 ||i >size){
            throw new MyArrayIndexOutOfBoundsException("指针越界异常:"+"i");
        }
        //和顺序表不一样了,不能通过索引直接定位,需要从头节点开始进行查找
        //从头节点开始移动指针
        Node p = head;
        for (int j = 0; j <= i; j++) {
            p = p.next;
        }
        return p.data;
    }

添加节点操作

添加节点不需要移动元素,只需要修改元素的指针
需要先查找到添加位置i,再添加新节点

public void add(int i, Object e) {
        //如果i的位置错误报异常
        if (i < 0 || i > size){
            throw new MyArrayIndexOutOfBoundsException("指针越界异常:"+"i");
        }
        //找到前一个节点,从头节点head开始移动指针
        Node p = head;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        //新创建一个节点
        Node newNode = new Node(e,null);
        //需要先指明新节点的直接后继节点,
        newNode.next = p.next;
        //再指明新节点的直接前驱节点
        p.next = newNode;
        //节点个数+1
        size++;
    }

删除节点操作

public Object remove(int i) {
        if (i < 0 || i > size){
            throw new MyArrayIndexOutOfBoundsException("指针越界异常:"+"i");
        }
        Node p = head;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        Node temp = p.next;
        p.next = temp.next;
        temp.next = null;
        size--;
        return temp.data;
    }
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
6个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(
22 22
4年前
【数据结构之链表】详细图文教你花样玩链表
【系列文章推荐阅读】0.提要钩玄文章已经介绍了链式存储结构,介绍了链式存储结构的最基本(简单)实现——单向链表。单向链表,顾名思义,它是单向的。因为单链表的每个结点只有一个数据域和一个指针域,而该指针域只存储了下一个结点的地址,所以我们只能通过某结点找到其直接后继结点,却不能通过某节点找到其直接前驱结点。此外,由于单链表到尾结点(链表的最后一
浪人 浪人
4年前
C++实现简单的单链表
下面实现的是一个简单的单链表功能不多,学习使用pragmaonceinclude<iostreamusingnamespacestd;classListEx{private:structNode{Nodenext;intdata;Node
Wesley13 Wesley13
3年前
275,环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。如果 pos 是 1,则在该链表中没有环。说明:不允许修改给定的链表。示例1:输入:head3,2,0,4,pos
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Stella981 Stella981
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Easter79 Easter79
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
Java实现单链表反转操作
单链表是一种常见的数据结构,由一个个节点通过指针方式连接而成,每个节点由两部分组成:一是数据域,用于存储节点数据。二是指针域,用于存储下一个节点的地址。在Java中定义如下:publicclassNode{privateObjectdata;//数据域privateNodenext;//指针域publicNo