【Java 数据结构】LinkedList 类和模拟实现链表

🔥博客主页🔥：【坊钰_CSDN博客】

欢迎各位点赞👍评论✍收藏⭐

1. 什么是 LinkedList ？

2 LinkedList 的使用

2.1 LinkedList 的构造

2.2 LinkedList 的常用方法

2.3 LinkedList 的遍历

3. 单链表的模拟实现

3.1 基本框架

3.2 头插

3.3 尾插

3.4 在第 pos 位后面插入 val

3.5 打印

3.6 求大小

4. 全部源码

5. 小结

1. 什么是 LinkedList ？

对于存储数据来说，ArrayList 是有缺陷的，ArrayList 动态扩容时可能会有空间的损失，而 LinkedList 的元素存储在特定的节点中，通过引用来联系元素之间的关系，效率较高

LinkedList 也是实现了 List 接口

LinkedList 的底层是使用了双链表
LinkedList 适合多次频繁插入和删除的场景

2 LinkedList 的使用

2.1 LinkedList 的构造

LinkedList 有两种构造方法

LinkedList()                            //空构造方法
LinkedList(Collection<? extends E>)     //以链表进行构造(必须为 E 的子类)

public class Test {
    public static void main(String[] args) {
        // 空构造
        LinkedList list1 = new LinkedList();

        // 以链表来构造
        LinkedList list2 = new LinkedList(list1);
    }
    
}

2.2 LinkedList 的常用方法

LinkedList 的常用方法和 ArrayList的常用方法基本一样，有兴趣可以看一下上一篇博客

【Java 数据结构】ArrayList 类与模拟实现顺序表-CSDN博客

2.3 LinkedList 的遍历

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // for-each 遍历
        for(Integer x : list)
            System.out.print(x);

        //使用迭代器遍历
        ListIterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

3. 单链表的模拟实现

3.1 基本框架

public class MyLinkedList {

    public static class LinkedNode {
        int value;
        LinkedNode next;

        LinkedNode(int value) {
            this.value = value;
        }
    }
}

3.2 头插

/*
 * 头插
 * */

public void addInsert(int val) {
    LinkedNode node = new LinkedNode(val);
    if (head == null) {
        head = node;
    } else {
        node.next = head;
        head = node;
    }
}

3.3 尾插

/*
 * 尾插
 * */

public void fastInsert(int val) {
    LinkedNode node = new LinkedNode(val);
    if (head == null) {
        head = node;
    } else {
        LinkedNode ret = head;
        while (ret.next != null) {
            ret = ret.next;
        }
        ret.next = node;
    }
}

3.4 在第 pos 位后面插入 val

/*
 * 在第 pos 位后面插入 val
 * */

public void posInsert(int pos,int val) {
    LinkedNode node = new LinkedNode(val);
    if (pos <= 0 || pos > linkSize()) {
        System.out.println("Pos is No !");
        return;
    }
    if (pos == linkSize()) {
        fastInsert(val);
        return;
    }
    int count = pos - 1;
    LinkedNode ret = head;
    while (count != 0) {
        ret = ret.next;
        count--;
    }
    node.next = ret.next;
    ret.next = node;

}

3.5 打印

/*
 * 打印
 * */

public void printList() {
    LinkedNode ret = head;
    while (ret != null) {
        System.out.print(ret.value+" ");
        ret = ret.next;
    }
    System.out.println();
}

3.6 求大小

/*
 * 求大小
 * */

public int linkSize() {
    int count = 0;
    LinkedNode ret = head;
    while (ret != null) {
        count++;
        ret = ret.next;
    }
    return count;
}

4. 全部源码

public class MyLinkedList {

    public static class LinkedNode {
        int value;
        LinkedNode next;

        LinkedNode(int value) {
            this.value = value;
        }
    }

    LinkedNode head;

    /*
     * 打印
     * */
    public void printList() {
        LinkedNode ret = head;
        while (ret != null) {
            System.out.print(ret.value+" ");
            ret = ret.next;
        }
        System.out.println();
    }

    /*
     * 求大小
     * */
    public int linkSize() {
        int count = 0;
        LinkedNode ret = head;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        return count;
    }


    /*
     * 头插
     * */
    public void addInsert(int val) {
        LinkedNode node = new LinkedNode(val);
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    /*
     * 尾插
     * */
    public void fastInsert(int val) {
        LinkedNode node = new LinkedNode(val);
        if (head == null) {
            head = node;
        } else {
            LinkedNode ret = head;
            while (ret.next != null) {
                ret = ret.next;
            }
            ret.next = node;
        }
    }

    /*
     * 在第 pos 位后面插入 val
     * */
    public void posInsert(int pos,int val) {
        LinkedNode node = new LinkedNode(val);
        if (pos <= 0 || pos > linkSize()) {
            System.out.println("Pos is No !");
            return;
        }
        if (pos == linkSize()) {
            fastInsert(val);
            return;
        }
        int count = pos - 1;
        LinkedNode ret = head;
        while (count != 0) {
            ret = ret.next;
            count--;
        }
        node.next = ret.next;
        ret.next = node;

    }
}