The article directories

  • Java – Single linked lists of data structures
  • 1. The concept and structure of linked lists
  • 2. Realization of single linked list
    • (1) Define a node type
    • (2) Head insertion method
    • (3) Tail insertion method
    • (4) Insert nodes according to subscripts
    • (5) Search keywords
    • (6) Delete the first occurrence of the keyword
    • (7) Get the length of the single linked list
    • (8) Single linked list printing display
    • (9) Node recovery
  • 3. Presentation of the complete code
  • Finished!

Java – Single linked lists of data structures

\

Follow up on Java – sequence tables of data structures

This content introduces the outline

\

\

In the previous study, we mainly understand a lot of Basic Syntax of Java, but in the later Java learning, it is very important to understand the knowledge of basic data structure, the idea of data structure can help us more clearly understand the idea of Solving problems in Java and so on.

Today we are going to start learning how to implement a Java-based single linked list.

\

1. The concept and structure of linked lists

\

A linked list is a kind of discontinuous storage structure in physical storage structure. The logical order of data elements is realized by reference link order in the linked list.

In practice, linked list structures are very diverse, and there are eight linked list structures when combined:

\

One way, two way

Lead, don’t lead

Cyclic, acyclic

Today, we implement a one-way, headless, acyclic linked list.

Here is the structure of the list.

\

2. Realization of single linked list

\

(1) Define a node type

\

We create a ListNode class as the node type, so how do we define member attributes?

From the above structural analysis, we need to define two member variables val — the stored value of this node, and next — to hold the address/reference of the next node.

Also, after definition, their default value is 0, null, so to assign the value to this node, write a constructor that first saves the value.

\

\

Here we provide two constructors, one to implement the node that provides the value, and the other to implement the node that does not provide the value, for our convenience later.

We then implement the various methods of the single list in the MyListNode class.

\



\

(2) Head insertion method



Take the above structure as an example, this single linked list has no special puppet node to act as the head node, the first node is defined as the head node, so the head interpolation method, we define a node, inserted at the front of the list, as the new head.

\

Code implementation:

1. Define an insert node

 ListNode cur = new ListNode(2);
Copy the code



At this point we create a node with val 2.

2. Insert it in front of the head node

There are two cases here,

The node is inserted for the first time

This is not the first time a node has been inserted

Structure after head insertion:

Code implementation:

\

(3) Tail insertion method

\

Similar to the head interpolation method, insert a node at the end of the list.



There are also two cases of insertion

The node is inserted for the first time

This is not the first time a node has been inserted

Code implementation:

\

(4) Insert nodes according to subscripts

\

The first data node is subscript 0 and the node is inserted anywhere.

Using the linked list above as an example, we want to insert the new node into position 2

If we want to insert into position 2, we need to change the properties of the original position 1 node and position 2 node.

Train of thought:

1. Check whether the index subscript is valid

2. If index==0 is passed, insert the header

3. If index==sizeof() is passed in, insert the end method

4. If sizeof() > index > 0 is inserted in the middle of the list, we first need to find prev at index-1

Search index – 1

Modify the properties of the PREv node and the properties of the new node

     node.next = prev.next
     prev.next = node;
Copy the code

Code implementation process

\

(5) Search keywords

\

For example, we will now look for the presence of a node in the list with val=20 and return true if there is one, false if there is none.

If cur.val == key, return true. If key is not found, return false.

\

(6) Delete the first occurrence of the keyword

\

Train of thought:

\

Code implementation:

\

\

(7) Get the length of the single linked list

\

\

(8) Single linked list printing display

\

It can’t be this.head. Next! = null so that the last node cannot be printed

\

(9) Node recovery

\

Nodes can be reclaimed in two ways:

1. The method of violence

Empty head directly

2. Empty them one by one

Iterate through the single linked list and set next to NULL for each node.

\

3. Presentation of the complete code

\





\

Well, today’s knowledge is shared here, I hope you can practice more, thank you for your appreciation and attention!


\

Thanks for your support!!


\

Finished!