Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to learn and master linked lists". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Brief introduction

A linked list (Linked List) is a common basic data structure, which is a linear table, but does not store data in a linear order, but a pointer (Pointer) to the next node in each node.

The linked list consists of two parts: the data field and the pointer field, and its structure is as follows:

Complexity analysis

Because linked lists do not need to be stored sequentially, linked lists can achieve O (1) complexity when inserted, which is much faster than sequential lists, but it takes O (n) time to find a node or access a specific numbered node, while sequential list insertion and query time complexity is 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, and the linked list structure can make full use of the computer memory space to realize flexible memory dynamic management. However, the linked list loses the advantage of random reading of the array, and the linked list has a large space overhead due to the increase of the pointer domain of the node.

classification

Linked lists are usually divided into the following three categories:

Unidirectional linked list

Bidirectional linked list

Cyclic linked list

Single linked list

Double cyclic linked list

1. Unidirectional linked list

The simplest type of linked list is an one-way linked list, or single linked list, which contains two fields, a data field and a pointer field, which is used to point to the next node, while the last node points to a null value, as shown in the following figure:

The traversal direction of a single linked list is single and can only be traversed from the beginning of the chain to the end of the chain. Its disadvantage is that when you want to query the previous node of a node, you can only traverse the query again from scratch, so the efficiency is relatively low, and the emergence of two-way linked list just solves this problem.

Next, we use code to implement the nodes of the one-way linked list:

Private static class Node {E item; Node next; Node (E element, Node next) {this.item = element; this.next = next;}}

two。 Bidirectional linked list

A two-way linked list is also called a double-sided linked list, and each node of it consists of three parts: the prev pointer points to the front node, and the data and next pointer of this node points to the back 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 item; Node next; Node prev; Node (Node prev, E element, Node next) {this.item = element; this.next = next; this.prev = prev;}}

3. Cyclic linked list

Circular linked list is divided into single circular linked list and double cyclic linked list, that is, the first and last nodes of one-way linked list or two-way linked list are connected, so that single-cyclic linked list or double-cyclic linked list is realized, as shown in the following figure:

Linked list in Java

After learning the basics of linked lists, let's consider a question: what type of linked list does LinkedList in Java belong to? One-way linked list or two-way linked list?

To answer this question, first look at the source code in JDK, as follows:

Package java.util; import java.util.function.Consumer; public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable {/ / linked list size transient int size = 0; / / linked list header transient Node first; / / linked list tail transient Node last; public LinkedList () {} public LinkedList (Collection

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.