Java数据结构链表

admin • 2024-04-04 20:29 • 物联网

无头单向不循环

物理上不一定连续，但逻辑上连续

链表是由一个一个的节点组织起来的，整体就叫做链表。

public class MySingleLinkedList {
    //将节点定义为内部类
    class ListNode{//节点有两个域
        public int val;
        public ListNode next;//next为引用类型

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//为链表的头节点

    public void createList(){
        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(代表整个对象，存地址）

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

head=head.next;

链表什么时候遍历完？

head为空时即head==null

为什么不是head.next==null?

会少打印一个值。如果要把每个结点的值都遍历完，head==null

public void display(){
        ListNode cur=head;//以防再遍历链表的时候找不到head
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

求长度：

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

插入结点的时候，一般首先绑后边

头插法：

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

public class Test {
    public static void main(String[] args) {
        MySingleLinkedList msl=new MySingleLinkedList();
        //msl.createList();此时这种琼剧创建链表的方式可以用插入来替代了
        msl.addFirst(1);
        msl.addFirst(2);
        msl.addFirst(3);
        msl.addFirst(4);
        msl.display();
        System.out.println(msl.size());
    }
}

尾插：

1.找到链表的尾巴

cur.next==null cur指向的就是尾巴

2.cur.next=node

public void addLast(int val){
        ListNode node=new ListNode(val);
        ListNode cur=head;
        //尾插需注意：cur.next 空指针异常
        if(head==null){
            head=node;//node为第一个节点
            return;
        }
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

在任意位置插入:

1.得找到index位置的前一个

cur走index-1步

2.如何连接？

3.index==0 头插

4.index==len 尾插

5.index不合法呢？即index<0 || index>len

查找链表中是否包含某个数

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

删除某个数

1.得找到那个数的前一个cur

if(cur.next.val==val)->找到了

2.删除

cur.next=del.next;

3.循环条件是什么

while(cur.next!=null)

if(cur.next.val==val)

public void remove(int 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;
        }
    }

但是还删不了头节点

public void remove(int val) {
        //空连表不可删
        if (head == null)
            return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }

删除所有需要删除的值

最后再删除头节点或者首先就用while循环一直删掉所有和值相等的头节点

cur代表当前需要删除的节点

prev代表当前需要删除节点cur的前驱节点

public void removeAllKey(int val){
        //1.判空
        if(head==null){
            return;
        }
        //2.定义 prev和null
        ListNode prev=head;
        ListNode cur=head.next;
        //3.开始判断并删除
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;//prev=prev.next;
            }
            cur=cur.next;
        }
        //4.处理头节点
        if(head.val==val){
            head=head.next;
        }
    }

完整代码：

public class MySingleLinkedList {
    //将节点定义为内部类
    class ListNode {//节点有两个域
        public int val;
        public ListNode next;//next为引用类型

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

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

    public void createList() {
        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;
        this.head = node1;
    }//当方法结束后node1 node2...这些变量都不存在了-局部变量被回收

    public void display() {
        ListNode cur = head;//因为此时为不带头链表，以防再遍历链表的时候找不到head
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

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

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

    public void addLast(int val) {
        ListNode node = new ListNode(val);
        ListNode cur = head;
        //尾插需注意：cur.next 空指针异常
        if (head == null) {
            head = node;//node为第一个节点
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    public void addIndex(int index, int val) {
        //1.判断index的合法性
        try {
            checkIndex(index);
        } catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        //2.index==0 || index==size()
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }
        //3.找到index的前一个位置
        ListNode cur = findIndexSubOne(index);
        //4.进行连接
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index) {
        int count = 0;
        ListNode cur = head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    private void checkIndex(int index) throws IndexNotLegalException {
        if (index < 0 || index > this.size()) {
            throw new IndexNotLegalException("index不合法");
        }
    }

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

    public void remove(int val) {
        //空连表不可删
        if (head == null)
            return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }

    public void removeAllKey(int val) {
        //1.判空
        if (head == null) {
            return;
        }
        //2.定义 prev和null
        ListNode prev = head;
        ListNode cur = head.next;
        //3.开始判断并删除
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
            } else {
                prev = cur;//prev=prev.next;
            }
            cur = cur.next;
        }
        //4.处理头节点
        if (head.val == val) {
            head = head.next;
        }
    }

    //清空
    public void clear() {
        // head=null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }
}

public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {
    }
    public IndexNotLegalException(String msg) {
        super(msg);
    }

}

无头双向不循环

任意位置插入

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

java 数据结构链表

二维码

【VUE+ElementUI】el-table表格固定列el-table__fixed导致滚动条无法拖动

< <上一篇

Spark安全日志分析与事件调查：实战指南

下一篇>>

搜索内容

Java数据结构链表

无头单向不循环

无头双向不循环

最新文章

分类

标签云