Java中的LinkedList

LinkedList是java.util包中集合框架的一部分。这个类是LinkedList数据结构的实现，其中元素不存储在连续的位置上，每个元素都是一个独立的对象，包含数据部分和地址部分。元素是通过指针和地址链接起来的。每个元素被称为节点。

由于其动态性和插入和删除的便利性，LinkedList比数组更受青睐。但它也有一些缺点，例如无法直接访问节点，而是需要从头开始，跟随链接到达我们想访问的节点。

LinkedList是如何工作的？

由于LinkedList作为动态数组，而我们不必在创建它时指定大小，因此当我们动态添加和删除项目时，列表的大小会自动增加。此外，元素不以连续的方式存储。因此，无需增加大小。在内部，LinkedList使用双向链表数据结构实现。

普通链表和双向链表的主要区别在于，双向链表包含一个额外的指针，通常称为前一个指针，以及单向链表中存在的下一个指针和数据。

LinkedList的构造函数：

要创建一个LinkedList，我们需要创建LinkedList类的对象。 LinkedList类包含各种构造函数，允许列表的可能创建。以下是此类中可用的构造函数：

1. LinkedList（）： 此构造函数用于创建一个空链表。如果我们希望创建一个名为ll的空LinkedList，则可以创建为：

LinkedList ll = new LinkedList（）;

2. LinkedList（Collection C）： 此构造函数用于创建一个有序列表，其中包含指定集合的所有元素，该元素由集合的迭代器返回。若要创建名为ll的LinkedList，则可以创建为：

LinkedList ll = new LinkedList（C）;

Java LinkedList的方法：

以下是以上操作的实现：

// Java程序演示
// LinkedList类的实现
 
// 导入所需的类
import java.util.*;
 
// 主类
public class GFG {
 
    // 驱动程序
    public static void main(String args[])
    {
        // 创建LinkedList类对象
        LinkedList<String> ll = new LinkedList<String>();
 
        // 将元素添加到链表中
        ll.add("A");
        ll.add("B");
        ll.addLast("C");
        ll.addFirst("D");
        ll.add(2, "E");
 
        System.out.println(ll);
 
        ll.remove("B");
        ll.remove(3);
        ll.removeFirst();
        ll.removeLast();
 
        System.out.println(ll);
    }
}

输出

[D, A, E, B, C]
[A]

在上面的示例中，AbstractList，CopyOnWriteArrayList和AbstractSequentialList是实现列表接口的类。每个提到的类中实现了单独的功能。它们是:

• AbstractList: 这个类用于实现一个不可修改的列表，只需要扩展这个AbstractList类并实现get()和size()方法即可。
• CopyOnWriteArrayList: 这个类实现了列表接口。它是ArrayList的增强版本，在其中所有的修改(add，set，remove等)都是通过重新复制列表来实现的。

LinkedList上执行各种操作:

• 添加元素
• 更新元素
• 删除元素
• 遍历元素
• To Array();
• Size();
• remove First();
• remove last();

操作1: 添加元素

为了将元素添加到LinkedList中，我们可以使用add()方法。根据不同的参数，重载了该方法以执行多个操作。它们是:

• add(Object): 此方法用于在LinkedList尾部添加元素。
• add(int index, Object): 此方法用于在LinkedList的特定索引处添加元素。

以下是以上操作的实现：

// Java程序添加元素
// to a LinkedList
 
import java.util.*;
 
public class GFG {
 
    public static void main(String args[])
    {
        LinkedList<String> ll = new LinkedList<>();
 
        ll.add("Geeks");
        ll.add("Geeks");
        ll.add(1, "For");
 
        System.out.println(ll);
    }
}

输出

[Geeks, For, Geeks]

操作2: 更改元素

添加元素后，如果我们希望更改元素，则可以使用set()方法。由于LinkedList是索引的，我们希望更改的元素是由元素的索引引用的。因此，此方法需要一个索引和需要插入到该索引的更新元素。

以下是以上操作的实现：

// Java程序用于修改LinkedList中的元素

import java.util.*;
 
public class GFG {
 
    public static void main(String args[])
    {
        LinkedList<String> ll = new LinkedList<>();
 
        ll.add("Geeks");
        ll.add("Geeks");
        ll.add(1, "Geeks");
 
        System.out.println("初始LinkedList " + ll);
 
        ll.set(1, "For");
 
        System.out.println("更新后的LinkedList " + ll);
    }
}

输出

初始LinkedList [Geeks, Geeks, Geeks]
更新后的LinkedList [Geeks, For, Geeks]

操作3：删除元素

为了从LinkedList中删除元素，我们可以使用remove()方法。该方法重载，根据不同的参数执行多个操作。它们是：

• remove(Object)： 该方法用于删除LinkedList中的一个对象。如果有多个这样的对象，则删除对象的第一个出现。
• remove(int index)： 由于LinkedList是索引的，因此该方法接受一个整数值，该值仅删除LinkedList中该特定索引处存在的元素。删除元素后，元素的索引会更新，因此LinkedList对象得到更新，给出删除元素后的新列表。

以下是上述操作的实现：

// Java程序用于删除LinkedList中的元素

import java.util.*;
 
public class GFG {
 
    public static void main(String args[])
    {
        LinkedList<String> ll = new LinkedList<>();
 
        ll.add("Geeks");
        ll.add("Geeks");
        ll.add(1, "For");
 
        System.out.println("初始LinkedList " + ll);
 
          // 调用函数
        ll.remove(1);
 
        System.out.println("索引删除后 " + ll);
 
        ll.remove("Geeks");
 
        System.out.println("对象删除后 "
                           + ll);
    }
}

输出

初始LinkedList [Geeks, For, Geeks]
索引删除后 [Geeks, Geeks]
对象删除后 [Geeks]

操作4：迭代LinkedList

有多种方法可以遍历LinkedList。最著名的方法是使用基本的for循环与get()方法组合以获取特定索引处的元素以及高级for循环。

以下是上述操作的实现：

// Java程序用于迭代LinkedList中的元素

import java.util.*;
   
public class GFG {
   
    public static void main(String args[])
    {
        LinkedList<String> ll
            = new LinkedList<>();
   
        ll.add("Geeks");
        ll.add("Geeks");
        ll.add(1, "For");
   
        //使用Get方法和for循环
        for (int i = 0; i < ll.size(); i++) {
   
            System.out.print(ll.get(i) + " ");
        }
   
        System.out.println();
   
        //使用for each循环
        for (String str : ll)
            System.out.print(str + " ");
    }
}

输出

Geeks For Geeks 
Geeks For Geeks 

操作4：使用toArray()方法将LinkedList转换为数组;

import java.util.*;
public class GFG2 {
    public static void main(String[] args)
    {
        LinkedList<Integer> list= new LinkedList<Integer>();
        list.add(123);
        list.add(12);
        list.add(11);
        list.add(1134);
        System.out.println("LinkedList: "+ list);
        Object[] a = list.toArray();
        System.out.print("转换为数组后的结果: ");
        for(Object element : a)
        System.out.print(element+" ");
    }
}

输出

LinkedList: [123, 12, 11, 1134]
转换为数组后的结果: 123 12 11 1134 

操作5-size();

import java.io.*;
import java.util.LinkedList;
public class GFG2 {
    public static void main(String args[]) {
        LinkedList<String> list = new LinkedList<String>();
        list.add("Geeks for Geeks ");
        list.add("是最好的 ");
        // 显示链表的大小
        System.out.println("链表的大小为: " + list.size());
    }
}

输出

链表的大小为: 2

操作7-removeFirst();

import java.io.*;
import java.util.LinkedList;
public class GFG2 {
    public static void main(String args[]) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("LinkedList:" + list);
        System.out.println("删除第一个元素后的链表: " + list.removeFirst());
        // 显示最终的链表
        System.out.println("Final LinkedList:" + list);
    }
}

输出

LinkedList:[10, 20, 30]
删除第一个元素后的链表: 10
Final LinkedList:[20, 30]

操作8-removeLast();

import java.io.*;
import java.util.LinkedList;
public class GFG2 {
    public static void main(String args[])
    {

        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("LinkedList:" + list);
        // 使用removeLast()方法删除最后一个元素
        System.out.println("删除最后一个元素后的链表: " + list.removeLast());
        // 显示最终的链表
        System.out.println("Final LinkedList:" + list);
        // 使用removeLast()方法删除最后一个元素
        System.out.println("删除最后一个元素后的链表: " + list.removeLast());
        // 显示最终的链表
        System.out.println("Final LinkedList:" + list);
    }
}

输出

LinkedList:[10, 20, 30]
删除最后一个元素后的链表: 30
Final LinkedList:[10, 20]
删除最后一个元素后的链表: 20
Final LinkedList:[10]

Java中的LinkedList类是Java Collections Framework的一部分，提供了List接口的链表实现。它允许在双向链表数据结构中存储和检索元素，其中每个元素都链接到其前任和后继元素。

以下是一个使用Java中LinkedList的简单示例：

import java.util.LinkedList;
 
public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个新的链表
        LinkedList<Integer> linkedList = new LinkedList<>();
 
        // 向链表中添加元素
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
 
        // 向链表的开头添加元素
        linkedList.addFirst(0);
 
        // 向链表的末尾添加元素
        linkedList.addLast(4);
 
        // 打印链表的元素
        for (int i : linkedList) {
            System.out.println(i);
        }
    }
}

输出

0
1
2
3
4

在Java中使用LinkedList的优点：

1. 动态大小：和Vector一样，LinkedList的大小可以动态增长或缩小，因此您不必担心设置初始大小。
2. 高效的插入和删除：LinkedList是一种高效的数据结构，用于在列表的中间插入或删除元素，因为您只需要更改元素之间的链接，而不是移动插入或删除点之后的所有元素。
3. 灵活的迭代：通过链表，您可以高效地迭代列表的每个元素，因为每个元素都有对其前​​驱和后继元素的引用。

在Java中使用LinkedList的缺点：

1. 性能：与ArrayList相比，在访问单个元素方面，LinkedList的性能较慢。这是因为您需要遍历列表才能到达所需的元素，而使用ArrayList，您可以通过索引简单地访问所需的元素。
2. 内存开销：LinkedList需要比ArrayList更多的内存，因为每个元素需要为与其前​​驱和后继元素的链接额外消耗内存。