【数据结构】无头单链表的实现 —— Java

seven_ • 2023年2月28日上午10:52 • 后端笔记 • 阅读 79

链表：

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的

其实呢，链表的结构非常多样，分为以下情况

单向双向
无头有头
循环非循环

这次呢，我们说说无头单向非循环链表

代码实现：

//结点类
class ListNode{
    public int data;
    public ListNode next;

    public ListNode(int data){
        this.data=data;
        this.next=null;
    }
}
//单链表类
public class MySignalList {
    public ListNode head;//head是引用
    //构造方法
    public MySignalList(){
        this.head=null;
    }
    //头插
    public void addFirst(int data){
        ListNode node=new ListNode(data);//创建一个结点，node代表当前对象引用
        //如果链表为空
        if (this.head==null){
            this.head=node;
        } else{
            node.next=this.head;
            this.head=node;
        }
    }
    //尾插
    public void addLast(int data){
        ListNode node=new ListNode(data);
        //链表为空
        if (this.head==null){
           this.head=node;
        } else {
            ListNode cur=this.head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }
    private ListNode searchIndex(int index){
        ListNode cur=head;
        while (index-1>0){
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (index<0||index>size()){
            System.out.println("位置不合法！");
            return false;
        }
        if (index==0){
            addFirst(data);
            return true;
        }
        else {
            ListNode cur = searchIndex(index);
            ListNode node=new ListNode(data);
            node.next=cur.next;
            cur.next=node;
            return true;
        }
    }
    //判断是否包含一个key
    public boolean contains(int key){
        ListNode cur=this.head;
        if (cur==null){
            System.out.println("链表为空！");
        }
        while (cur!=null){
            if (cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //链表的长度
    public int size(){
        ListNode cur=head;
        int count=0;
        if (cur==null){
            return 0;
        }
        else {
            while(cur!=null){
                count++;
                cur=cur.next;
            }
            return count;
        }
    }
    //打印单链表
    public void display(){
        ListNode cur=this.head;
        while(cur!=null){
            System.out.println(cur.data);
            cur=cur.next;
        }
    }
}

对无头节点单链表的主要操作就是 头插法，尾插法，任意节点插入。

头插法：