【Java–数据结构】Java链表新手指南:从零开始,轻松构建你的数据链!

欢迎关注个人主页:逸狼

创造不易,可以点点赞吗~

如有错误,欢迎指出~

目录

顺序表的缺点

链表

模拟实现链表

创建MySingleLidnkedList类和测试类Test

定义节点和创建链表的方法

 测试

 结果

 打印链表和求链表长度

测试

结果

头插法

 测试

结果

尾插法

任意位置插入

测试

结果

 删除任意值val

测试

结果

删除所有val值

测试

结果

清空链表


顺序表的缺点

对于ArrayList来说,不方便插入和删除,因为要移动元素。比如,最坏的情况:0下标插入,删除0下标,都要移动所有元素。

扩容可能会浪费空间,假设100个空间,要放101个数据(进行1.5倍扩容,得150个空间),但实际只放了101个,剩下49个空间就浪费了

为了解决以上问题:链表他来了~

链表

有八种结构

  • 链表结构在逻辑上是连续的,但物理上不一定连续
  • 现实中的节点一般是从堆上申请的

模拟实现链表

创建MySingleLidnkedList类和测试类Test

定义节点和创建链表的方法

public class MySingleLinkedList {

    //定义节点类   内部类
    class ListNode{
        public int val;
        public ListNode next;

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

    public ListNode head;//代表链表的头节点

    public void createList(){
        //node1等为局部变量 当createList调用完之后,会node1等会消失
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5=null;
        this.head=node1;
    }
}

 测试

        MySingleLinkedList msl=new MySingleLinkedList();
        msl.createList();//创建好了五个节点的链表

 结果

 打印链表和求链表长度

有两个问题

1 怎么从第一个节点走到第二个节点

head=head.next

2 链表什么时候遍历完

head==null(若条件是 head.next==null则会导致最后一个节点不会打印)

    打印链表

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


    //求链表长度
    public int size(){
        int count=0;
        ListNode cur=head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

测试

        
        msl.display();
        System.out.println(msl.size());

结果

头插法

先实例化一个节点,将数据放入节点。

  • node.next=head;
  • head=node;

(插入数据时一般先绑后面,防止数据丢失)

注意:空链表时也可以使用该代码,因为node.next和head本身都为空,所以不影响;

    //头插法
    public void addFirst(int val){
        ListNode node=new ListNode(val);
        node.next=head;
        head=node;
    }

 测试

        msl.addFirst(1);
        msl.addFirst(4);
        msl.addFirst(3);
        msl.addFirst(2);

结果

尾插法

需要找到链表的尾巴(假设找到的尾节点是cur)

  • 遍历(进入while循环)条件是cur.next!=null(想象此时cur是最后一个节点,cur.next==null,不能进入循环,即cur找到了尾节点)
  • cur=cur.next;

cur.next=node

    //尾插法
    public void addLast(int val){
        ListNode node=new ListNode(val);
        if(head==null){
            head=node;
            return;
        }
        ListNode cur=head;
        while(cur.next!=null){

            cur=cur.next;
        }
        cur.next=node;
    }

任意位置插入

先找到index-1位置的节点(假设是节点cur)

  • node.next=cur.next
  • cur.next=node

还要注意以下特殊情况

  • index==0 ->头插
  • index==len->尾插
  • index非法(index<0和index>链表长度)情况,此时可以抛出异常(自己定义的)
    //任意位置插入
    public void addIndex(int index,int val){
        //1.判断index的合法性
        try{
                findIndexSubOne(index);
        }catch(IndexNotLegalException e){
            e.printStackTrace();
        }

//        2.index==0||index==size();
        if(index==0){
            addFirst(val);
            return;
        }
        if(index==size()){
            addLast(val);
            return;
        }
        ListNode node=new ListNode(val);
//        3.找到Index前一个位置
        ListNode cur=findIndexSubOne(index);
//        链接
        node.next=cur.next;
        cur.next=node;

    }
    //找Index前一个位置
    private ListNode findIndexSubOne(int index) {
        ListNode cur=head;
        for (int i = 0; i < index-1; i++) {
            cur=cur.next;
        }
        return cur;
    }
    //判断Index是否合法
    private void checkIndex(int index)throws IndexNotLegalException{
        if(index<0||index>size()){
            throw new IndexNotLegalException("Index不合法。。。");
        }
    }

测试

        msl.addFirst(4);
        msl.addFirst(3);
        msl.addFirst(2);
        msl.addFirst(1);
        msl.display();

        msl.addIndex(0,9);
        msl.display();

        msl.addIndex(2,99);
        msl.display();

        msl.addIndex(msl.size(), 999);
        msl.display();

结果

 删除任意值val

利用循环条件cur.next!=null找到值为val的前一个节点

找到cur后,定义被删的节点del=cur.next,让cur.next=del.next,完成删除操作

注意

  • 处理空链表:判断head为空后,直接return
  • 处理头节点是要删的节点:head=head.next;
    //删值为val的值
    public void remove(int val){
        if(head==null){
            return;
        }
        //删头节点
        if(head.val==val){
            head=head.next;
            return;
        }
        //找到val前一个节点
        ListNode cur=head;
        while(cur.next!=null){
            if(cur.next.val==val){
                ListNode del=cur.next;
                cur.next=del.next;
                return;
            }
            cur=cur.next;
        }
    }

测试

        MySingleLinkedList msl=new MySingleLinkedList();
        msl.addLast(11);
        msl.addLast(22);
        msl.addLast(33);
        msl.addLast(44);
        msl.display();

        msl.remove(11);
        msl.remove(33);
        msl.display();

结果

删除所有val值

定义cur是遍历节点,pre是cur的前驱节点

如果cur的值为val,

  • pre.next=cur.next
  • cur=pre.next

否则,

  • pre=cur
  • cur=cur.next

注意

  • 处理空链表:判断head为空后,直接return
  • 处理头节点是要删的节点:head=head.next,使用while循环防止前面都是要删的节点情况;
    //删除所有val值
    public void removeAllVal(int val){
        if(head==null){
            return;
        }
        //删头节点
        while(head.val==val) {
            head = head.next;
        }
        ListNode pre=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                pre.next=cur.next;
            }else{
                pre=cur;
            }
            cur=cur.next;
        }
    }

测试

        msl.addFirst(4);
        msl.addFirst(4);
        msl.addFirst(3);
        msl.addFirst(2);
        msl.addFirst(4);
        msl.addFirst(1);
        msl.display();
        msl.removeAllVal(4);
        msl.display();

结果

清空链表

//清空链表
    public void clear(){
        //法1
//        head=null;
        //法2 遍历,将每个节点都置为空
        ListNode cur=head;
        while(cur!=null){
            ListNode curN=cur.next;
//            cur.val=null;//如果是引用类型就置为null
            cur.next=null;
            cur=curN;
        }
        head=null;
    }

 

版权声明:本文为博主作者:逸狼原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/2301_80898480/article/details/138134798

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
扎眼的阳光的头像扎眼的阳光普通用户
上一篇 2024年5月6日
下一篇 2024年5月6日

相关推荐