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

In this article, the editor introduces in detail the method of adding, deleting, changing and searching the Java linked list. The content is detailed, the steps are clear, and the details are handled properly. I hope that this article "the method of adding, deleting, changing and searching the Java linked list" can help you solve your doubts.

I. the concept and structure of linked lists 1.1 the concept of linked lists

To put it simply, a linked list is a data structure that is not necessarily physically continuous, but logically continuous.

1.2 Classification of linked lists

In practice, the structure of linked list is very diverse, and there are 8 kinds of linked list structure in the following cases. One-way and two-way, leading and non-leading, cyclic and non-circular. There will be 8 kinds of permutations and combinations.

But I only have two kinds of linked lists that are more difficult to implement, and the other six are easier to understand.

1. One-way non-leading acyclic linked list

two。 Two-way non-leading acyclic linked list

II. One-way unled acyclic linked list 2.1 create node types

We created a ListNode class as the node type with two member variables, val to store values and next to store the address of the next node.

There is also a constructor with one parameter that instantiates the object and assigns a value to val, because we don't know the address of the next node, so next is the default value, a null.

Class ListNode {public int val;// numeric public ListNode next;// address of the next node public ListNode (int val) {this.val = val;}}

We create a head variable in MyLinkedList to identify the head of the linked list, and then add, delete and change the single linked list.

2.2 head insertion

This head insertion method does not consider the first insertion. For each insertion, you only need to change the next value of the inserted node node to the head node, and then point the head node to node.

/ / public void addFirst (int data) {ListNode node = new ListNode (data); node.next = this.head; this.head = node;} 2.3 tail insertion

Tail insertion should first consider whether it is the first time to insert. If so, point the head directly to node. If not, you need to define a cur to find the tail node and change the next value of the tail node to node. Because if you don't use the tail node, the head can't be identified to the head.

/ / public void addLast (int data) {ListNode node = new ListNode (data); ListNode cur = this.head; / / insert if for the first time (this.head = = null) {this.head = node;} else {while (cur.next! = null) {cur = cur.next;} cur.next = node;}} 2.4 to get the list length

Define a counter count. When cur finishes traversing the linked list, it just returns count.

/ / get the length of the single linked list public int size () {int count = 0; ListNode cur = this.head; while (cur! = null) {cur = cur.next; count++;} return count;} 2.5 insert at any position

We assume that the head of the linked list starts at position 0, and there are several points to consider when inserting at any position.

1. The validity of the position. If the position is less than 0 or greater than the length of the linked list, the position is illegal.

two。 If you want to insert the 0 position, use the head insertion method directly.

3. If the insertion position is equal to the length of the linked list, then use tail interpolation, because our linked list starts at 0.

The most important thing is to insert from anywhere in the middle to insert from the middle, you need to find the location of the previous node where you want to insert it. And insert it between them.

/ * Let cur take the index-1 step back * @ param index * @ return * / public ListNode findIndexSubOne (int index) {int count = 0; ListNode cur = this.head; while (count! = index-1) {cur = cur.next; count++;} return cur } / / insert at any location, the first data node is 0 subscript public void addIndex (int index,int data) {/ / judge validity if (index)

Size () {System.out.println ("invalid index position"); return;} / / head insertion if (index = = 0) {this.addFirst (data); return;} / / tail insertion if (index = = size ()) {this.addLast (data); return } / / find the leading driver. Cur points to the previous node of index ListNode cur = findIndexSubOne (index); ListNode node = new ListNode (data); node.next = cur.next; cur.next = node;} 2.6.Lookup keywords

When we want to find out if there is a keyword in the linked list, we just need to define a cur to traverse from scratch.

/ / find whether the keyword key is included in the single linked list public boolean contains (int key) {ListNode cur = this.head; while (cur! = null) {if (cur.val = = key) {return true;} cur = cur.next;} return false;} 2.7.Delete the node whose value is key for the first time

This idea is actually very simple, considering two situations.

1. If you want to delete the header node, you only need to point the header node to one of its facing nodes.

two。 There is also a case where key does not exist, so a method is written here to determine whether key exists, and if so, return the location of the previous node of key.

3. If it exists, change the next of the precursor of the node to be deleted to its next.

/ * find the previous node where you want to delete key * @ return * / public ListNode searchPrev (int key) {ListNode prev = this.head; while (prev.next! = null) {if (prev.next.val = = key) {return prev;} prev = prev.next;} return null } / / Delete the node whose keyword is key for the first time: public void remove (int key) {if (this.head.val = = key) {this.head = this.head.next; return;} / / find the precursor node of key ListNode prev = searchPrev (key); if (prev = = null) {System.out.println ("no key keyword"); return } / / Delete ListNode delete = prev.next; prev.next = delete.next;} 2.8.Delete all nodes with a value of key

Suppose you want to delete 3, train of thought:

A variable that defines two node types, prev pointing to head,cur pointing to the next node of head.

If it is determined that the value of cur is the value to be deleted, if so, skip this node directly. If not, let prev and cur go back until the entire linked list is traversed.

In the end, you will find that the header node has not been traversed, and after the loop, you need to determine whether the header node is the node to be deleted.

Remember to write code while drawing!

/ / delete all nodes with a value of key public void removeAllKey (int key) {ListNode prev = this.head; ListNode cur = this.head.next; while (cur! = null) {if (cur.val = = key) {prev.next = cur.next; cur = cur.next;} else {prev = cur; cur = cur.next }} / / determine whether the first node is the node to be deleted if (this.head.val = = key) {this.head = this.head.next;}} 2.9 traversal print list

Just define a cur to traverse and print directly.

/ / print the linked list public void display () {ListNode cur = this.head; while (cur! = null) {System.out.print (cur.val+ ""); cur = cur.next;} System.out.println ();}

Empty linked list

You only need to empty the linked list one by one, and it is not recommended to directly empty the header node.

/ / empty linked list public void clear () {ListNode cur = this.head; / / one empty while (cur! = null) {ListNode curNext = cur.next; cur.next = null; cur = curNext;} this.head = null;} III. Bi-directional non-cyclic linked list

The biggest difference between two-way linked list and one-way linked list is that there is one more precursor node prev, which also realizes the addition, deletion, query and modification of two-way linked list.

Public class TestLinkedList {public ListNode head; public ListNode last;} 3.1 create Node Type

Also define the node type first, with one more precursor node than the one-way linked list.

Class ListNode {public int val; public ListNode prev; public ListNode next; public ListNode (int val) {this.val = val;}}

The two-way linked list also defines a last to identify the tail node, while the single linked list only identifies the header node.

3.2 head insertion

Because this is a two-way linked list, the first insertion is to have head and last point to the first node at the same time.

If this is not the first time to insert, you need to

1. Change the precursor node of head to node

two。 Then change node's next to head.

3. Then point the header node head to the new header node node.

/ / public void addFirst (int data) {ListNode node = new ListNode (data); / / insert if for the first time (this.head = = null) {this.head = node; this.last = node;} else {head.prev = node; node.next = this.head; this.head = node;}

The two-way linked list has a last to identify the tail node, so there is no need to look for the tail node when inserting the tail. Similar to plug insertion.

/ / insert public void addLast (int data) {ListNode node = new ListNode (data); / / insert if (this.head = = null) {this.head = node; this.last = node;} else {this.last.next = node; node.prev = this.last; this.last = node;}} for the first time to get the list length

This is the same as a single linked list, which directly defines a cur traversal

/ / get the length of the linked list public int size () {ListNode cur = this.head; int count = 0; while (cur! = null) {count++; cur = cur.next;} return count;} 3.5 insert at any position

Arbitrary insertion is also similar to a single linked list in three cases. Judge the legitimacy and head-to-tail insertion is not much, mainly in the middle of the random insertion, we must pay attention to the order of modification!

There are four changes to be made, so you must draw a picture and understand it!

/ / find the location of the node to be inserted public ListNode searchIndex (int index) {ListNode cur = this.head; while (index! = 0) {cur = cur.next; index--;} return cur;} / / insert at any location. The first data node is the 0 subscript public void addIndex (int index,int data) {/ / judge the validity of the index location if (index)

This.size () {System.out.println ("illegal position of index"); return;} / / head insertion if (index = = 0) {this.addFirst (data); return;} / / tail insertion if (index = = this.size ()) {this.addLast (data); return } / / insert ListNode node = new ListNode (data); ListNode cur = searchIndex (index); node.next = cur; node.prev = cur.prev; cur.prev.next = node; cur.prev = node;} 3.6.Lookup keywords

Here, just like a single linked list, just define a cur traversal to see if there is this value in the linked list.

/ / find whether to include the keyword key in the single linked list public boolean contains (int key) {ListNode cur = this.head; while (cur! = null) {if (cur.val = = key) {return true;} cur = cur.next;} return false;} 3.7.Delete the node where the keyword key appears for the first time

Idea: go through the linked list to find the node that appears for the first time, and delete the return. There are three situations.

1. The header node is the node to be deleted

two。 The tail node is the node to be deleted

3. The middle node is the node to be deleted

/ / delete the node whose keyword is key for the first time: public void remove (int key) {ListNode cur = this.head; while (cur! = null) {if (cur.val = = key) {/ / the header node if (this.head = = cur) {this.head = this.head.next; this.head.prev = null } else {/ / tail node and middle node cur.prev.next = cur.next; if (this.last = = cur) {/ / delete tail node cur = cur.prev } else {cur.next.prev = cur.prev;}} / / return;} else {cur = cur.next;} 3.8 Delete all nodes with a value of key

The idea is similar to deleting a key, but there are two points to note.

1. Do not use return after deletion, but continue to go back, because here is to delete all for key, you need to traverse the list

two。 There is also to consider that when the entire linked list is to be deleted, if will judge that otherwise a null pointer exception will occur.

/ / delete all nodes with a value of key public void removeAllKey (int key) {ListNode cur = this.head; while (cur! = null) {if (cur.val = = key) {/ / the header node if (this.head = = cur) {this.head = this.head.next / / assume that all the nodes to be deleted are if (this.head! = null) {this.head.prev = null;} else {/ / prevent the last node from being recycled this.last = null }} else {/ / tail node and middle node cur.prev.next = cur.next; if (this.last = = cur) {/ / delete tail node cur = cur.prev } else {cur.next.prev = cur.prev;}} / / one step cur = cur.next;} else {cur = cur.next;}} 3.9 traversal print linked list / / print linked list public void display () {ListNode cur = this.head While (cur! = null) {System.out.print (cur.val+ ""); cur = cur.next;} System.out.println ();}

Empty linked list

Traverse the linked list one by one to null, and then set the head node and tail node value to null. Prevent memory leaks

/ / empty linked list public void clear () {ListNode cur = this.head; / / one empty while (cur! = null) {ListNode curNext = cur.next; cur.prev = null; cur.next = null; cur = curNext;} this.head = null; this.last = null } after reading this, the article "the method of adding, deleting, changing and querying Java linked list" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, welcome to follow the industry information channel.

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.