当前位置：首页 > article >正文

【数据结构与算法】Java描述：第二节：LinkedList 链表

article 2025/3/11 5:18:53

一、链表的概念与结构

1.1 概念：

通俗的来说，链表是由一个个结点连接起来的就叫链表。

1.2 结构：

链表存储的数据在 物理上是不一定连续的，它是由前面链接后面，一个个连起来的。

二、Java底层的 LinkedList

2.1 Java底层构成：

LinkedList 的底层是 双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的j结点中，然后通过引用将结点连接起来了。

因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

LinkedList 中包含 LinkNode 类

从上图我们可以看到每个结点都有三部分构成，

分别是数据 (elem)，结点的前驱 (prev)，结点的后继(next)

2.2 链表的构造方法：

和顺序表类似，可以传入另一个链表作为参数来创建新的链表

三、链表相关方法

3.1 链表中的方法：

3.2 链表的遍历

public static void main(String[] args) {
        LinkedList<Integer> linkedList2 = new LinkedList<>();
        linkedList2.add(1);//默认都是尾插
        linkedList2.addLast(3);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        System.out.println(linkedList2);
        
        //迭代器反向遍历
        System.out.println("===== ListIterator ====");
        ListIterator<Integer> lit2 =  linkedList2.listIterator(linkedList2.size());
        while (lit2.hasPrevious()) {
            System.out.print(lit2.previous()+" ");
        }
        System.out.println();

        //迭代器正向遍历，属于子类
        System.out.println("===== ListIterator ====");
        ListIterator<Integer> lit =  linkedList2.listIterator();
        while (lit.hasNext()) {
            System.out.print(lit.next()+" ");
        }
        System.out.println();
        
        //迭代器正向遍历
        System.out.println("===== Iterator ====");
        Iterator<Integer> it = linkedList2.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();

        //for each遍历
        System.out.println("=====for each====");

        for(Integer x : linkedList2) {
            System.out.print(x +" ");
        }
        System.out.println();
        
        //for循环遍历
        System.out.println("=====for====");
        for (int i = 0; i < linkedList2.size(); i++) {
            System.out.print(linkedList2.get(i) +" ");
        }
        System.out.println();


    }