Java linear list chain storage – single linked list

As we all know, the storage structure of linear table is divided into two kinds, sequential storage structure and chain storage structure, the classification of linear table can refer to the following figure to learn and remember. Today we’re going to focus on chain storage.

First, chain storage introduction

“Chained storage structure, address can be contiguous or discontiguous storage cells store data elements” — from definition.

Actually, you can imagine such A scene, you want to find A man (his name is XiaoTan), so the first thing you ask A, A, said he did not know, but he said B may know, and tell you where is the B, then you find B, B said he did not know, but he said C may know, and tell you the address of the C, So you go to C. C. really knows where Tan is.

The above scenario can actually help us to understand the linked list, in fact every list contains more than one node, the node and contains two parts, one is the data fields (storage nodes contain information), is a pointer field (stored on the next node or a node address), and the pointer field is equivalent to you ask B, B know C address, This pointer field is the address where C is stored.

There are three types of linked lists: single linked lists, bidirectional linked lists and circular linked lists. Today we’re going to start with singly linked lists.

Introduction of single linked list

What is a singly linked list? A singly linked list is a list with only one pointer field per node. The figure below shows a singly linked list of leading nodes. Next we need to know what a header pointer, a header node and a header node are.

Header pointer: A pointer to the first node of a linked list node

Head node: a node that precedes the first member of the list

Primary node: a node that stores the first actual data element in a linked list (such as a1 in the figure above)

Three, the creation of a single linked list

There are two ways to create a single linked list, namely, the head interpolation method and the tail interpolation method.

1. Head insertion method

Header insertion, as the name implies, is to insert a new element into the header position, each time the new element is added as the first node of the list. So how do you implement header insertion in Java? First we need to define a node, as follows

public class ListNode { public int val; Public ListNode next; // pointer field}Copy the code

Then we create a header pointer (no leading node)

Int n = 5; ListNode headNode = new ListNode(); // headNode= createHead(headNode, n);Copy the code

Create a private method to implement the headinsert method. Here we insert 5 new elements. The core of the headinsert method is to disconnect the headNode from the head pointer. Next = newNode. These two steps are the core of header insertion.

/** ** new node is placed after the head node, @param headNode * @return */ private static ListNode createHead(ListNode headNode, Int n) {// Insert 5 new nodes for (int I = 1; i <= n; i++) { ListNode newNode = new ListNode(); newNode.val = i; Newnode.next = headNode.next; newNode.next = headNode.next; Headnode. next = newNode; } return headNode; }Copy the code

Finally, I print out the linked list (in fact, it is also a single linked list traversal), judging the condition is only when the pointer field is empty is the last node.

private static void printLinkedList(ListNode headNode) { int countNode = 0; while (headNode.next ! = null){ countNode++; System.out.println(headNode.next.val); headNode = headNode.next; } system.out.println (" The total number of nodes in this single list: "+countNode); }Copy the code

The final output is obviously in reverse order, because none of the new elements are inserted from the header, so the first element is the last, and the last element is the first:

2. Tail insertion method

Tail insertion, as the name implies, is the insertion of a new element into the tail position (that is, the last position), each new element is the last node of the list. So how to implement tail insertion method in Java, here is still not the implementation of the head node, the head node and the head pointer and the implementation of the head insert the same way, here I will directly how to implement:

/** ** find the end of the list, * @param headNode */ private static ListNode createByTail(ListNode headNode, ListNode tailNode = headNode; ListNode tailNode = headNode; for (int i = 1; i <= n; i++) { ListNode newNode = new ListNode(); newNode.val = i; newNode.next = null; // Insert into the list tailnode. next = newNode; Tailer always stores the address of the last node tailNode = newNode; } return headNode; }Copy the code

Unlike header insertion, we need to declare a tail pointer to assist us in implementing this implementation. Initially, the tail pointer points to the head pointer, and each time we insert an element, the tail pointer moves back. Here’s how it works: Each time we add a newNode to the end, we need to disconnect the original connection. So how do we disconnect? We first need to make the tail pointer point to the newNode. Then move the tail pointer back one position so that it points to the last node. That is, the tail pointer always points to the last node, and finally returns the head pointer to print the final result:

Delete single linked list

Now that the single linked list has been created, how to delete elements in the single linked list? I have divided the deletion of the single linked list into two cases, namely, deleting the ith node and deleting the node of the specified element.

1. Delete the ith node

In single-linked lists, nodes are linked by pointer fields, so if we want to delete the operation, we actually need to change the corresponding pointer field to the address due. When we want to delete the ith element, such as the third element in the figure above, we need to change the pointer field of element 2 to store element 4. So how do you get there? Obviously, to do this, we need to find element 4 and element 2, but if you think about it, we only need to find element 2, because the address of element 4 is stored in the pointer field of the element 2 after it.

Therefore, we can conclude from the above analysis that there are two core steps of deletion:

1. To delete the i-th node, find the i-1st node, that is, the previous node of the i-th node.

2. Then make the i-1 node point to the next node after the i-1 node

The following code specifies how to remove the ith element.

* @param headNode * @param index * @return */ public static ListNode deleteNodeByIndex(ListNode headNode, int index) { int count = 1; // will refer to it ListNode preNode = headNode; While (prenode.next!) (prenode.next! = null &&count <= index -1){// Find the previous node count++ of the current node to delete; preNode = preNode.next; } if (preNode ! = null){ preNode.next = preNode.next.next; } return headNode; }Copy the code

2, delete the node of the specified element

There are two ways to delete the specified element node. The first way is to find the position (index) of the linked list corresponding to the specified element, and then delete the ith node according to the same idea. The implementation method is shown in the figure below:

/** * private static ListNode deleteNodeByNum(ListNode headNode, ListNode headNode,  int val) { ListNode deleteOne = headNode; int countByDeleteOne = 1; while (deleteOne.next ! = null){ if (deleteOne.next.val == val){ deleteOne = deleteOne.next; break; } countByDeleteOne ++; deleteOne = deleteOne.next; } return deleteNodeByIndex(headNode, countByDeleteOne); }Copy the code

The implementation of the second method is subtle (provided that this node is not a tail node)

Public void deleteNode(ListNode node) {// deleteNode by assigning the following value to node and changing the pointer to the next node. node.next = node.next.next; }Copy the code

Five, single linked list query (and modification)

The query implementation of single linked list is very simple, is to traverse the current single linked list, and then use a counter to add up to the current index, so the current node is the node to query, and then return, of course, need to judge whether the subscript passed is legal. Of course, if you need to modify, you need to re-assign the value of the node data field that needs to be modified, so there is no code here. The concrete implementation is as follows:

private static ListNode searchLinkedList(ListNode headNode, Int index) {/ / if it is illegal to subscript subscript said can't find the if (index < 1 | | index > getLinkedListLength (headNode)) {return null; } for (int i = 0; i < index; i++) { headNode = headNode.next; } return headNode; }Copy the code

Get the length of the single linked list (note that I defined headNode here as a head pointer, not a headNode)

Private static int getLinkedListLength(ListNode headNode) {int countNode = private static int getLinkedListLength(ListNode headNode) {int countNode = 0; while (headNode.next ! = null){ countNode++; headNode = headNode.next; } return countNode; }Copy the code

Six, the summary

Singly linked lists related operations are finished, actually in the face of singly linked lists related operations, through it is not hard to find, delete, and insert singly linked lists are actually very convenient, only need to change a pointer pointing to complete, but look for the element is more troublesome, because at the time of search, need the whole list traversal time from beginning to end.

Finally, recently, many friends asked me for Linux learning roadmap, so I stayed up for a month in my spare time according to my own experience, and sorted out an e-book. Whether you are interviewing or self-improvement, I believe will help you! The directory is as follows:

Free to everyone, just ask everyone to point to me!

Ebook | Linux development learning roadmap

Also hope to have a small partner can join me, do this e-book more perfect!

Have a harvest? Hope the old iron people come to a triple whammy, give more people to see this article

Recommended reading:

  • Dry goods | programmers advanced architect necessary resources free of charge
  • Artifact | support resource site search