Principle of linked list and Java implementation code example

1： Basic introduction to one-way linked list

A linked list is a data structure at the same level as an array. For example, the implementation principle of ArrayList in Java is array. The implementation principle of LinkedList is linked list. The linked list is inefficient in circular traversal, but it has obvious advantages in insertion and deletion. The following is an introduction to the one-way linked list.

Concept of single linked list

Linked list is the most basic data structure. The schematic diagram of its storage is shown in the figure below

The above shows the storage schematic diagram of a single linked list. It is easy to understand. Head is the head node. It does not store any data, but acts as a point to the first node in the linked list that actually stores data, and each node has a next reference to the next node. In this way, it records down section by section until the last node, Where next points to null.

There are many kinds of linked lists, such as single linked list, double linked list and so on. We will learn about the single linked list. Others understand that the principle is actually the same.

One way linked list is a linear list, In fact, it is composed of nodes. A linked list has an indefinite number of nodes. Its data storage in memory is discontinuous. Its stored data is scattered in memory. Each node can only and only it can know the storage location of the next node. It is composed of N nodes (nodes) form a one-way linked list. Each node records the data of this node and the next node. Only one head node is exposed. All our operations on the linked list are carried out directly or indirectly through its head node.

The leftmost node in the figure above is the head node, but the order of adding nodes is from right to left, and the added new node will be regarded as a new node. The reference of the first added node to the next node can be empty. The reference is an object that references the next node rather than the next node. Because there are constant references, the head node can operate all nodes.

The following figure describes the storage of one-way linked list. Storage is decentralized. As long as each node records a node, it strings all data to form a one-way linked list.

A node consists of an object to be stored and a reference to the next node. That is, a node has two members: a stored object and a reference to the next node. The following figure is a specific description:

2、 Implementation of single linked list

3、 Common operation implementation methods related to linked list

1. Linked list inversion

2. Find the intermediate node of the single linked list

Use the fast and slow pointer to find the intermediate node of the single linked list. The fast pointer takes two steps at a time and the slow pointer takes one step at a time. When the fast pointer is finished, the slow pointer just reaches the intermediate node.

3. Find the last K element

Two pointers P1 and P2 are used. P1 moves forward K steps, and then P1 and P2 move at the same time. When P1 moves to the tail, the element at the position indicated by P2 is the penultimate element.

4. Sort the linked list

5. Delete duplicate nodes in the linked list

6. Output the single linked list from end to end, which is realized by recursion

7. Judge whether the linked list has a ring. If there is a ring, find the entry node of the ring

summary

The above is all about the principle of linked list and Java implementation code examples in this paper. I hope it will be helpful to you. Interested friends can continue to refer to this website:

Java programming to realize the merging of incremental sorting linked lists

Java interview questions - copy and code sharing of complex linked lists

The penultimate node in the Java output linked list