23 pictures! Ten thousand words explain the “linked list”, from Xiaobai to big brother!
Linked list and array are two important and commonly used basic data types in data types. Array is a data structure continuously stored in memory. Therefore, its advantage is that it can quickly find the location of elements through subscripts, while its disadvantage is that a large number of elements will be forced to move when inserting and deleting elements, In order to solve and balance this problem, there is a linked list data type.
Linked lists and arrays can form effective complementarities, so that we can select the corresponding data types according to different business scenarios. In this article, let's focus on learning the linked list. First, it's very important. Second, it's necessary for the interview. Let's take a look at the outline of this article first:
After watching some anti Japanese dramas, we all know that in order to prevent the members of the organization from being "end-to-end", some secret organizations usually use the way of single line contact between superiors and subordinates to protect other members, and this "behavior" is the main feature of the linked list.
brief introduction
Linked list is a common basic data structure. It is a linear table, but it does not store data in linear order, but saves the pointer of the next node in each node.
The linked list is composed of data field and pointer field. Its structure is as follows:
Complexity analysis
Because the linked list does not need to be stored in order, the complexity of inserting the linked list can reach o (1), which is much faster than that of the sequential list. However, it takes O (n) time to find a node or access a node with a specific number, while the time complexity of inserting and querying the sequential list are o (log n) and O (1) respectively.
Analysis of advantages and disadvantages
Using the linked list structure can overcome the disadvantage that the array linked list needs to know the data size in advance. The linked list structure can make full use of the computer memory space and realize flexible memory dynamic management. However, the linked list loses the advantage of random reading of arrays. At the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of nodes.
classification
Linked lists are usually divided into the following three categories:
1. One way linked list
The simplest type of linked list is one-way linked list, or single linked list. It contains two fields, a data field and a pointer field. The pointer field is used to point to the next node, and the last node points to a null value, as shown in the following figure:
Next, we use code to implement the nodes of the one-way linked list:
private static class Node<E> {
E item;
Node<E> next;
Node(E element,Node<E> next) {
this.item = element;
this.next = next;
}
}
2. Two way linked list
The two-way linked list is also called double-sided linked list. Each node consists of three parts: the prev pointer points to the front node, and the data and next pointer of this node point to the rear node, as shown in the following figure:
Next, we use code to implement the nodes of the two-way linked list:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev,E element,Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
3. Circular linked list
Circular linked list is divided into single circular linked list and double circular linked list, that is to connect the head and tail nodes of one-way linked list or two-way linked list, so as to realize single circular linked list or double circular linked list, as shown in the following figure:
Linked list in Java
After learning the basic knowledge of linked list, let's think about a question: what type of linked list does the linked list in Java belong to? One way linked list or two-way linked list?
To answer this question, first let's look at the source code in the JDK, as follows:
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>,Deque<E>,Cloneable,java.io.Serializable
{
// 链表大小
transient int size = 0;
// 链表头部
transient Node<E> first;
// 链表尾部
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
// 获取头部元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 获取尾部元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
// 删除头部元素
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 删除尾部元素
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 添加头部元素
public void addFirst(E e) {
linkFirst(e);
}
// 添加头部元素的具体执行方法
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null,e,f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 添加尾部元素
public void addLast(E e) {
linkLast(e);
}
// 添加尾部元素的具体方法
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l,null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 查询链表个数
public int size() {
return size;
}
// 清空链表
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// 根据下标获取元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev,Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 忽略其他方法......
}
It can be seen from the definition of the above node: LinkedList is actually a two-way linked list, because it defines two pointers, next and prev, which are used to point to its next and previous nodes respectively.
Common methods of linked list
The design of LinkedList is still very clever. After understanding its implementation code, let's take a look at how it is used? Or what are its common methods.
1. Increase
Next, let's demonstrate the use of the addition method:
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.add("Java");
list.add("中文");
list.add("社群");
list.addFirst("头部添加"); // 添加元素到头部
list.addLast("尾部添加"); // 添加元素到最后
System.out.println(list);
}
}
The execution result of the above code is:
In addition to the above three addition methods, LinkedList also includes other addition methods, as shown below:
The difference between add and offer
Their differences are mainly reflected in the following two points:
2. Delete
The demo code for deleting the function is as follows:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("头部");
list.offer("中间");
list.offer("尾部");
list.removeFirst(); // 删除头部元素
list.removeLast(); // 删除尾部元素
System.out.println(list);
}
}
The execution result of the above code is:
In addition to the above deletion methods, more deletion methods are as follows:
3. Modification
The demonstration code of the modification method is as follows:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MysqL");
list.offer("DB");
// 修改
list.set(2,"Oracle");
System.out.println(list);
}
}
The execution result of the above code is:
4. Query
The demonstration code of the query method is as follows:
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.offer("Java");
list.offer("MysqL");
list.offer("DB");
// --- getXXX() 获取 ---
// 获取最后一个
System.out.println(list.getLast());
// 获取首个
System.out.println(list.getFirst());
// 根据下标获取
System.out.println(list.get(1));
// peekXXX() 获取
System.out.println("--- peek() ---");
// 获取最后一个
System.out.println(list.peekLast());
// 获取首个
System.out.println(list.peekFirst());
// 根据首个
System.out.println(list.peek());
}
}
The execution result of the above code is:
5. Traversal
The traversal method of LinkedList includes the following three methods.
Traversal method 1:
for (int size = linkedList.size(),i = 0; i < size; i++) {
System.out.println(linkedList.get(i));
}
Traversal method 2:
for (String str: linkedList) {
System.out.println(str);
}
Traversal method 3:
Iterator iter = linkedList.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
Linked list application: queue & Stack
1. Realize stack with linked list
Next, we use the linked list to implement a first in first out "queue". The implementation code is as follows:
LinkedList list = new LinkedList();
// 元素入列
list.add("Java");
list.add("中文");
list.add("社群");
while (!list.isEmpty()) {
// 打印并移除队头元素
System.out.println(list.poll());
}
The results of the above procedures are as follows:
2. Queue with linked list
Then we use the linked list to implement a last in first out "stack". The implementation code is as follows:
LinkedList list = new LinkedList();
// 元素入栈
list.add("Java");
list.add("中文");
list.add("社群");
while (!list.isEmpty()) {
// 打印并移除栈顶元素
System.out.println(list.pollLast());
}
The results of the above procedures are as follows:
Linked list usage scenario
As a basic physical structure, linked list is often used to build many other logical structures, such as stack and queue, which can be implemented based on linked list.
Common written test questions in linked list
The most common written test question of linked list is the reversal of linked list. The previous article "two implementation methods of linked list reversal, the latter one beat 100% of users!" We provide two methods of linked list inversion, and in this paper, we will expand and provide three methods of linked list inversion.
Implementation method 1: stack
Let's illustrate the specific process of using the stack to reverse the linked list, as shown in the figure below.
Stack all:
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
stack.push(head); // 存入第一个节点
while (head.next != null) {
stack.push(head.next); // 存入其他节点
head = head.next; // 指针移动的下一位
}
// 反转链表
ListNode listNode = stack.pop(); // 反转第一个元素
ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 当前节点
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
return listNode;
}
The leetcode verification results are shown in the following figure:
Implementation method 2: recursion
Similarly, let's illustrate the specific process of this method in a graphical way, as shown in the figure below.
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 从下一个节点开始递归
ListNode reverse = reverseList(head.next);
head.next.next = head; // 设置下一个节点的 next 为当前节点
head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
return reverse;
}
The leetcode verification results are shown in the following figure:
Implementation method 3: loop
We can also reverse the linked list through a loop, but this method does not need to call its own method repeatedly. It only needs a loop. The implementation code is as follows:
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
// 最终排序的倒序链表
ListNode prev = null;
while (head != null) {
// 循环的下个节点
ListNode next = head.next;
// 反转节点操作
head.next = prev;
// 存储下个节点的上个节点
prev = head;
// 移动指针到下一个循环
head = next;
}
return prev;
}
}
The leetcode verification results are shown in the following figure: