【Java数据结构 -- 实现单链表的接口方法】

2023-12-13 20:43:10

1 链表的引入

当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构

2 链表的说明

链表是一种物理存储结构上非连续存储结构,逻辑上是连续的,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表的结构多样,下面情况组合有8种链表结构

  1. 单向或者双向
    在这里插入图片描述
  2. 带头或者不带头
    在这里插入图片描述
  3. 循环或者不循环
    在这里插入图片描述
    重要的两个链表:单链表和无头双向链表,下面所讲到就是单链表(无头单向非循环链表)

3 单链表

单链表是一种常见的线性数据结构,用于储存一系列具有相同类型的元素它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针单链表可以通过指针的方式实现元素的增删改查等方法

3.1 单链表的创建

用面向对象来把单链表封装成一个类,然后写一个静态内部类,类中的成员变量val,指向下一个节点的指针next,获取val的构造方法,最后再定义一个头节点。

public class MySingleList implements IList{

    static class ListNode {
        public int val;
        public ListNode next;

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

3.2 单链表的打印

遍历链表的时候通常需要定义一个临时cur来从头节点遍历,目的是防止head头节点丢失。循环条件cur != null,每次打印一个元素,cur都需要移动到下一个节点,即:cur = cur.next

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next; //让cur这个节点 可以从一个节点走到下一个节点
        }
        System.out.println();
    }

3.3 单链表是否存在某个元素

遍历链表,判断cur.val == key

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

3.4 单链表当前节点个数

    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) { // 代表整个链表走完了
            count++;
            cur = cur.next;
        }
        return count;
    }

3.5 单链表的头插法

在头节点插入新的节点,让该节点成为新的头节点。如果head头节点为空,直接将插入的node节点设为头节点即head = node,如果不为空,把插入节点指向下一个节点的next设为head,把node插入head之前,再把head重新设为node,即node.next = head

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

3.6 单链表的尾插法

如果链表为空,直接插入,不为空cur遍历链表,循环条件是cur.next != null,即cur.next == null的时候,cur指向的是最后一个节点,然后cur.next = node注意:cur == null时链表已经走完。

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
        }else {
            ListNode cur = head;
            while (cur.next != null) { // cur.next == null的时候,cur指向的是最后一个节点
                cur = cur.next;
            }
            cur.next = node;
        }
    }

3.7 单链表获取某个索引的节点

定义一个计数器count,循环条件count != index-1,让cur一直走到index

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

3.8 单链表往指定索引位置插入

判断索引位置是否合法,如果链表为空,直接插入,如果index==0,头插法,然后是在最后一个位置插入即index == size(),尾插法,中间插入的话先调用searchPreIndex方法获取到该索引的节点,然后先把cur后面的数据接到node.next防止数据丢失,即node.next = cur.next,再把node连接上cur.next即:cur.next = node

    @Override
    public void addIndex(int index, int data) throws IndexException{
        if (index < 0 || index > size()) {
            throw new IndexException("index不合法"+index);
        }
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }

        // 中间插入
        ListNode cur = searchPreIndex(index);
        node.next = cur.next;
        cur.next = node;
    }

3.9 单链表删除数据

定义一个指针 走到要删除的节点的前一个节点, 如果cur.next == key cur就是要删除节点的前驱,如果head为空返回空,如果删除的是头节点,直接将头节点的下一个节点设头节点,即head = head.next。写一个findPreKey方法来找到删除元素的节点,如果cur为空,即没有要删除的数字。把要删除的数据的下一个节点连上删除节点的前驱next。即:cur.next = del.next

    @Override
    public void remove(int key) {
        if (head == null) {
            return;
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = findPreKey(key);
        if(cur == null){
            return; //没有你要删除的数字
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    private ListNode findPreKey(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }else {
                cur = cur.next;
            }
        }
        return null;
    }

3.10 删除所有元素为key的节点

如果head为空返回空,定义一个prev,和一个cur为prev的下一个节点,循环条件为cur != null走完链表,如果cur.val == key,进行删除操作,prev.next = cur.next;cur = cur.next;即如下图:
在这里插入图片描述如果不是要删除的数据,prev和cur往下一走,即
prev = cur; cur = cur.next;

以上把除了头节点都删完了,如果头节点的值是要删的,直接head = head.next

    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode prev = head;
        ListNode cur = prev.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }  //除了头节点都删完了

        if (head.val == key) { // head头节点为想要删的值
            head = head.next;
        }
    }

3.11 回收链表

    // 当一个对象 没有人引用的时候 就会被回收掉
    @Override
    public void clear() {
        head = null;
    }

文章来源:https://blog.csdn.net/m0_63440113/article/details/134908495
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。