JAVA 实现单向链表 Linked

说明

单链表里面的数据元素是以结点为单位,每个结点是由数据元素的数据和下一个结点的地址组成

在java集合框架里面 LinkedListHashMap(数组加链表)等等的底层都是用链表实现的。

链表结果

添加元素

删除

特点

  • 数据元素在内存中存放的 地址是不连续的:单链表的结点里面还定义一个结点,它里面保存着下一个结点的内存地址,在实例化对象的时候,jvm会开辟不同内存空间,并且是不连续的。

  • 添加效率高:添加一个元素时,先找到插入位置的前一个,只需要将1,2个元素的连接断开,将插入结点的next指向第一个元素的next

java

节点类

/**
 * 节点类
 * @author mym
 *
 */
public class Node {

    private Object data;
    private Node next;

    public Node(Object data) {
        this.data = data;
    }
    public Object getData() {
        return data;
    }
    public void setData(Object data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

链表类


public class MyLinked {

    /**
     * 第一个节点
     */
    private Node head;
    /**
     * 链表长度,即:节点数量
     */
    private int size = 0;

    /**
     * 在尾部添加节点
     * @param data
     */
    public void add(Object data){
        add(size,data);
    }
    /**
     * 插入节点
     * @param index
     * @param data
     */
    public void add(int index,Object data){
        // 索引校验
        if(index < 0){
            throw new IndexOutOfBoundsException("index 不能小于 0");
        }
        // index 可以等于 size(长度),表示插入到末尾,但不能大于size(长度)
        if(index > size){
            throw new IndexOutOfBoundsException("index 不能大于长度,长度是: "+size);
        }
        Node node = new Node(data);
        if(index == 0){ // 头部插入节点
            if( head == null){ // 如果链表是空,没有元素
                head = node;
            }else{ // 如果链表不为空,有元素
                node.setNext(head);
                head = node;
            }
        }else{ // 中间添加节点、或 尾部添加节点
            Node temp = head;
            // 循环取出添加节点的前一个位置
            for(int i = 1; i<index;i++){
                temp = temp.getNext();
            }
            Node oldNext = temp.getNext();
            // 让前一个节点指向新节点
            temp.setNext(node);
            // 新节点指向原来的下一个节点
            node.setNext(oldNext);
        }
        size ++;
    }
    /**
     * 根据索引取出节点
     * @param index
     * @return
     */
    public Object get(int index){
        // 索引校验
        if(index < 0){
            throw new IndexOutOfBoundsException("index 不能小于 0");
        }
        if(size == 0){
            throw new IndexOutOfBoundsException("长度是: "+size+",没有元素");
        }
        if(index >= size){
            throw new IndexOutOfBoundsException("index 不能大于等于长度,长度是: "+size);
        }
        Node ret = null;
        if(index == 0){ // 取出第一个节点
            ret = head;
        }else{ // 取出中间阶段
            Node temp = head;
            // 循环指定的索引位置,取出该节点
            for(int i = 0; i<index;i++){
                temp = temp.getNext();
            }
            ret = temp;
        }
        return ret.getData();
    }
    /**
     * 删除指定索引的节点
     * @param i
     * @return
     */
    public Object remove(int index){
        // 索引校验
        if(index < 0){
            throw new IndexOutOfBoundsException("index 不能小于 0");
        }
        if(size == 0){
            throw new IndexOutOfBoundsException("长度是: "+size+",没有元素");
        }
        if(index >= size){
            throw new IndexOutOfBoundsException("index 不能大于等于长度,长度是: "+size);
        }
        Node ret = null;
        if(index == 0){ // 删除第一个节点
            ret = head;
            // 将第一个节点的下一个节点作为第一个节点
            head = head.getNext(); 
        }else{ // 取出中间阶段
            Node temp = head;
            // 循环,取出要删除节点的前一个节点
            for(int i = 0; i<index-1;i++){
                temp = temp.getNext();
            }
            //取出要删除的节点
            ret = temp.getNext();
            // 取出要删除节点的下一个节点
            Node next = ret.getNext();
            // 让前一个节点,指向下一个节点
            temp.setNext(next);
        }
        size--;
        return ret.getData();
    }
    public int size(){
        return size;
    }

}

测试类

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TestLinked {

    public static void main(String[] args) {
        MyLinked link = new MyLinked();

        link.add(0,"李雷");
        link.add("韩梅梅");
        link.add(0,"lucy");
        link.add(2,"lili");
        link.add(link.size(),"张三");

//        Object obj2 = link.remove(0);
//        System.out.println("删除:"+obj2);
//        
//        Object obj3 = link.remove(link.size()-1);
//        System.out.println("删除:"+obj3);

        Object obj3 = link.remove(2);
        System.out.println("删除:"+obj3);

        System.out.println("----");
        // 遍历
        for(int i = 0;i<link.size();i++){
            Object obj = link.get(i);
            System.out.println(obj);
        }

    }
    public static void main2(String[] args) {
        // 测试校验
        MyLinked l = new MyLinked();
        l.add("李雷");
//        l.add(-10, "");
//        l.add(10, "");

//        l.get(-10);
//        l.get(10);
//        l.get(0);
//        l.remove(-10);
        l.remove(10);
    }
    public static void main1(String[] args) {
        List list = new ArrayList();

//        list.add("李雷");
//        list.add(-1,"");
//        list.add(5, "韩梅梅"); //java.lang.IndexOutOfBoundsException
//        list.get(2);
        list.get(0);

        LinkedList ll = new LinkedList();

    }
}

参考

https://blog.csdn.net/m0_51724241/article/details/124307269

https://www.javazhiyin.com/72610.html


原文出处:http://malaoshi.top/show_1IX3bVPX5UuZ.html