Java LinkedList - Java 中的 LinkedList

Java LinkedList 是 List 和 Deque 接口的实现。它是最常用的 List 实现类之一。它扩展了 AbstractSequentialList 并实现了 List 和 Deque 接口。它是一个有序集合，支持重复元素。它按插入顺序存储元素。它支持添加空元素。它支持基于索引的操作。如果您想了解有关 List 基础知识的更多信息，请阅读这篇文章：Java List。

文章简要目录

在这篇文章中我们将讨论以下概念。

• Java 链表
• Java LinkList 类图
• Java LinkList 列表方法
• Java LinkList Deque 方法
• Java LinkedList 基本示例
• Java LinkedList 泛型
• Java 数组转为 LinkedList
• Java LinkedList 到数组
• Java LinkedList 实时用例
• Java LinkedList 的内部表示
• Java LinkedList 中的插入是如何进行的？
• Java LinkedList 中如何进行删除？
• Java LinkList Deque 操作
• Java SE 8：Java LinkedList 到 Stream
• Java SE 9 链接列表

Java 链表

在本节中，我们将讨论有关 Java LinkedList 的一些要点：

• Java LinkedList 类是 Java 集合框架的一个成员。
• 它是 List 和 Deque 接口的实现。
• 在内部，它是使用双向链表数据结构实现的。
• 它支持重复元素。
• 它按插入顺序存储或维护其元素。
• 我们可以添加任意数量的空元素。
• 它不是同步的，这意味着它不是线程安全的。
• 我们可以使用 Collections.synchronizedList() 方法创建一个同步的 LinkedList。
• 在Java应用程序中，我们可以将其用作列表，堆栈或队列。
• 它没有实现 RandomAccess 接口。所以我们只能按顺序访问元素。它不支持随机访问元素。
• 当我们尝试从 LinkedList 访问元素时，将根据元素可用的位置从 LinkedList 的开头或结尾开始搜索该元素。
• 我们可以使用 ListIterator 来迭代 LinkedList 元素。
• 从 Java SE 8 开始，我们可以将 LinkedList 转换为 Stream，反之亦然。
• Java SE 9 将添加几个工厂方法来创建 Immutable LinkedList。

Java LinkList 类图

我们知道，Java LinkedList 是 List 实现类之一。它还实现了 Deque。如下面的类图所示，它不是直接从 AbstractList 类扩展而来。它扩展了 AbstractSequentialList 类。

Java LinkList 列表方法

在本节中，我们将讨论一些有用且常用的 Java LinkedList 方法。以下方法继承自 List 或 Collection 接口：

1. int size()：获取列表中元素的数量。
2. boolean isEmpty()：检查列表是否为空。
3. boolean contains(Object o)：如果此列表包含指定元素，则返回 true。
4. 迭代器 iterator()：按正确顺序返回此列表中元素的迭代器。
5. Object[] toArray(): Returns an array containing all of the elements in this list in proper sequence.
6. boolean add(E e): Appends the specified element to the end of this list.
7. boolean remove(Object o): Removes the first occurrence of the specified element from this list.
8. boolean retainAll(Collection c): Retains only the elements in this list that are contained in the specified collection.
9. void clear(): Removes all the elements from the list.
10. E get(int index): Returns the element at the specified position in the list.
11. E set(int index, E element): Replaces the element at the specified position in the list with the specified element.
12. ListIterator listIterator(): Returns a list iterator over the elements in the list.
13. List subList(int fromIndex, int toIndex): Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa.

Java LinkedList Deque Methods

The following methods are specific to LinkedList class which are inherited from Deque interface:

1. void addFirst(E e): Inserts the specified element at the beginning of this list.
2. void addLast(E e): Inserts the specified element at the end of this list.
3. E getFirst(): Retrieves, but does not remove, the first element of this list. This method differs from peekFirst only in that it throws an exception if this list is empty.
4. E getLast(): Retrieves, but does not remove, the last element of this list. This method differs from peekLast only in that it throws an exception if this list is empty.
5. E remvoeFirst(): Removes and returns the first element from this list.
6. E removeLast(): Removes and returns the last element from this list.
7. boolean offerFirst(E e): Inserts the specified element at the front of this list.
8. boolean offerLast(E e): Inserts the specified element at the end of this list.
9. E pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.
10. E pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.
11. E peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
12. E peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

Java LinkedList Basic Example

In this section, we will discuss about Java LinkedList basic example. We will explore some more useful operations in the coming sections. Example:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo
{
  public static void main(String[] args)
  {
	List names = new LinkedList();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        names.add(2011);

	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

Output:-

LinkedList content: [Rams, Posa, Chinni, 2011]
LinkedList size: 4

Here we have created a LinkedList object and added 4 items. As we discussed LinkedList.size() method is used to get the number of elements in the list. NOTE:- Without using Generics, Java LinkedList supports Heterogeneous elements. However, it is not recommended to use Collections without Generics. Let us explore Java Generics Advantages and usage in the coming section with one simple example.

Java LinkedList Generics

In this section, we will discuss on how to use Generics with Java LinkedList. As we know, Java Generics are useful to write Type Safety programming and do Stronger type checks at compile time. They are also useful to eliminate the casting overhead. Example:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListGenericsDemo
{
  public static void main(String[] args)
  {
	List<String> names = new LinkedList<>();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        // We cannot add other than Strings
        // names.add(2011);

	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

Output:-

LinkedList content: [Rams, Posa, Chinni]
LinkedList size: 3

Here we have created a LinkedList object with Generics and added 3 items. When we try to add a Number for LinkedList, it throws compile-time error.

Java Array to LinkedList

In this section, we will explore how to convert a Java Array to LinkedList object. We can do it in many ways, however I have given only one approach here. Example:-

import java.util.LinkedList;
import java.util.List;

public class JavaArrayToLinkedListDemo
{
	public static void main(String[] args)
	{
		Integer[] numbers = {1,2,3,4,5};
		List<Integer> numbersList = new LinkedList<>();
		for(Integer s : numbers){
			numbersList.add(s);
		}
		System.out.println(numbersList);
	}
}

Output:-

[1, 2, 3, 4, 5]

Java LinkedList to Array

In this section, we will explore how to convert a Java LinkedList to an Array. We can do it in many ways, however I have given only one approach here. Example:-

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LinkedListToJavaArrayDemo
{
	public static void main(String[] args)
	{
		List<Integer> numbersList = new LinkedList<>();
		numbersList.add(1);
		numbersList.add(2);
		numbersList.add(3);
		numbersList.add(4);
		numbersList.add(5);
		Integer[] numbers = new Integer[numbersList.size()];

		numbers = numbersList.toArray(numbers);
		System.out.println(Arrays.toString(numbers));

	}
}

Output:-

[1, 2, 3, 4, 5]

Java LinkedList Real-time Usecases

In this section, we will discuss about what is the best and what is the worst case scenarios to use LinkedList in Java applications. Best Usecase scenario:-

• When our frequently used operation is adding or removing elements in the middle of the List, LinkedList is the best class to use.

Why? Because we don’t need to do more shifts to add or remove elements at the middle of the list. Please refer “How Insertion works in J Java LinkedList?” section to understand it in-detail. Worst Usecase scenario:-

• When our frequently used operation is retrieving elements from list, then LinkedList is the worst choice.

Why? Because LinkedList supports only sequential access, does NOT support random access. Please refer “How Deletion works in J Java LinkedList?” section to understand it in-detail. NOTE:- LinkedList implements List, Deque, Cloneable and Serializable. But it does NOT implement RandomAccess interface.

Internal Representation of Java LinkedList

As we know, internally Java LinkedList is implemented using Doubly Linked List. So Java LinkedList represents it’s elements as Nodes. Each Node is divided into 3 portions as shown below. Here each Node is used for a specific purpose.

1. Left side Node Part is used to point to the previous Node (Or Element) in the LinkedList.
2. Right side Node Part is used to point to the next Node (Or Element) in the LinkedList.
3. Center Node Part is used to store actual data.

NOTE:- In JVM, LinkedList does NOT store it’s elements in consecutive order. It stores it’s elements at any available space and they are connected each other using Left and Right side Node portions as shown in the below diagram.

How Insertion works in Java LinkedList?

We have already seen how LinkedList stores it’s elements as Nodes in the previous section. In this section, we will discuss about how Java LinkedList’s Insertion operation works internally.

1. Let us assume our initial LinkedList has the following data. 3. Perform the following Insertion operation on this LinkedList

linkedList.add(2,54);

Here we are trying to perform Insertion operation to add new element with value “54” at index 2.5. Updated LinkedList looks like below.

How Deletion works in Java LinkedList?

We have already seen how LinkedList performs Insertion operation internally in the previous section. In this section, we will discuss about how Java LinkedList’s Deletion operation works internally.

1. Let us assume our initial LinkedList has the following data. 3. Perform the following Insertion operation on this LinkedList

linkedList.remove(3);

Here we are trying to perform Deletion operation to delete an element which is available at index 3.5. Updated LinkedList looks like below.

Java LinkedList Deque Operations

Here we will explore how a LinkedList object works as a Deque. We use these operations to implement Queues or Stacks. We will discuss how a Stack or Queues works in-depth in my coming posts. Example:-

import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeOperationsDemo
{
  public static void main(String[] args)
  {
	Deque names = new LinkedList();
	names.add(2);
	names.addFirst(1);
	names.addLast(3);
	names.addFirst(0);
	names.addLast(4);

	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
	names.removeFirst();
	names.removeLast();

	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

Output:-

LinkedList content: [0, 1, 2, 3, 4]
LinkedList size: 5
LinkedList content: [1, 2, 3]
LinkedList size: 3

Java SE 8: Java LinkedList to Stream

Here we will explore how to convert a LinkedList object to Java SE 8 Stream concept. Example:-

import java.util.LinkedList;
import java.util.List;

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

	//convert List to stream
	numbersList.stream().forEach(System.out::println);
  }
}

Output:-

1
2
3
4
5

Java SE 9 LinkedList

In Java SE 9, Oracle Corp is going to add some useful utility methods to create Immutable List. If you want to learn them in-depth with some useful examples, please go through my post at: Java SE 9: Factory Methods for Immutable List That’s all of a quick roundup on LinkedList in Java. I hope these Java LinkedList examples will help you in getting started with LinkedList programming. Thank you for reading my tutorials. Please drop me a comment if you like my tutorials or have any issues or suggestions or any type errors.