Java-----链表

本篇碎碎念：唐朝诡事录中的西安与洛阳让我想到了，远赴人间惊鸿宴会，一睹人间盛世颜，描绘的就是这两个古都吧，有机会一定要去游览一番? ? ? ? ? ? ? ? ? ??

今日份励志文案:?最好的状态就是向自己喜欢的东西一点点靠近

一.链表的简单介绍

?2. 带头或者不带头

3. 循环或者非循环

二.链表的实现?

首先先定义出一个链表

static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }

    //链表的属性，链表的头节点
    public ListNode head;//null

    public void creatList(){

        ListNode node1=new ListNode(11);
        ListNode node2=new ListNode(22);
        ListNode node3=new ListNode(33);
        ListNode node4=new ListNode(44);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;

        this.head=node1;
    }

?

使用画图来表示链表的形式

2.1头插法：在链表起始位置加入一个元素

public void addFirst(int data) {

        ListNode node11=new ListNode(data);
        node11.next=head;
        head=node11;

    }

2.2尾插法：在链表的末尾位置加入一个元素

注意:在添加时要注意这个链表是不是为空，若为空直接添加为头节点即可

public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cue = head;
        if (cue == null) {
            cue.next = head;
            cue.next = node;
            node.next = null;
            return;
        }
        else {
            while (cue.next != null) {
                cue = cue.next;
            }
            cue.next = node;
            node.next = null;
        }
    }

2.3任意位置插入一个数据节点：

将date加入到index位置

注意:?

1.在添加时要注意添加的位置是否小于0 或者比链表的长度大

2.注意是不是添加到首段或者是末尾，那样直接使用头插法或者尾插法即可

3.index如果等于1 ，说明找到了插入的位置，因为链表的顺序是从0开始的

看下图，蓝色表示最开始所指向的位置，绿色表示经过一次循环后所指向的位置

public void addIndex(int index, int data) {

        if(index<0||index>size()){
            System.out.println("不合法");
        }

        ListNode node = new ListNode(data);
        ListNode cue = head;
        ListNode cue1=cue;

        if(index==0){
            addFirst(data);
            return;
        }

        if (index==size()){
            addLast(data);
            return;
        }

        while (index!=1){
            index--;
            cue=cue.next;
            cue1=cue.next;
        }
        cue.next=node;
        node.next=cue1;
    }

2.4查找是否包含关键字key是否在单链表当中

这个就是遍历然后查找key，在就返回ture，不在就返回false

  public boolean contains(int key) {
        ListNode cur=head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }

        return false;
    }

2.5删除第一次出现关键字为key的节点

注意:?

1.要注意是否为空指针

2.如果head与key相等可以直接返回

3.遍历寻找while中的if表示的是cue.next.val

public void remove(int key) {

        if (head==null){
            return;
        }

        if(head.val==key){
            head=head.next;
            return;
        }

        ListNode cue = head;
        ListNode del = head;

        while (cue.next!=null){
            if(cue.next.val==key){
                del=cue.next;
                cue.next=del.next;
                return;
            }
            cue=cue.next;
        }
        if(cue==null)
        {
            System.out.println("对不起没有要删除的数字");
        }
    }

public void removeAllKey(int key) {
        if (head==null){
            return;
        }

        ListNode prev = head;
        ListNode cue = head.next;

        while (cue!=null){
            if(cue.val==key){
                prev.next=cue.next;
                cue=cue.next;
            }
            else {
                prev=cue;
                cue=cue.next;
            }
        }

        if (head.val==key){
            head=head.next;
            return;
        }


    }

 public int size() {
        ListNode cur=head;
        int count=0;
        while (cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }

public void display() {
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

public interface IList {
        //public class SingleLinkedList {
        //头插法
        void addFirst(int data);
        //尾插法
        void addLast(int data);
        //任意位置插入,第一个数据节点为0号下标
        void addIndex(int index,int data);
        //查找是否包含关键字key是否在单链表当中
        boolean contains(int key);
        //删除第一次出现关键字为key的节点
        void remove(int key);
        //删除所有值为key的节点
        void removeAllKey(int key);
        //得到单链表的长度
        int size();
        void display();
        // }

}

public class demo1 implements IList{

    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
}

public class Test {
    public static void main(String[] args){
        demo1 demo=new demo1();
        demo.creatList();

        demo.display();
        demo.size();

        System.out.println();
        System.out.println(demo.contains(22));
        System.out.println(demo.contains(99));

        //头插法
        demo.addFirst(10);
        demo.display();

        //尾插法
        demo.addLast(55);
        demo.display();

        demo.addIndex(2,88);
        demo.display();
        demo.addIndex(0,1);
        demo.addIndex(0,1);
        demo.addIndex(3,1);
        demo.addIndex(3,1);
        demo.display();

        demo.remove(1);
        demo.display();

        demo.removeAllKey(1);
        demo.display();
    }
}

如果有解释的不对或者不清晰，如果可以从评论区指出，我一定会加以修改，万分感谢

希望对你们有所帮助