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

This article mainly explains the "detailed introduction of JAVA single linked list", the content of the article is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "JAVA single linked list detailed introduction" bar!

Catalogue

I. linked list

1. Concept

two。 structure

One-way non-leading acyclic linked list

1. Concept and structure

two。 Realization of linked list

First, linked list 1. Concept

A linked list is a discontinuous storage structure on the physical storage structure, and the logical order of data elements is realized through the reference link order in the linked list.

The sequence table described in the previous chapter is suitable for query and modification, not for insertion and deletion. And when it increases capacity, it is easy to cause space waste. The linked list has the following characteristics

Suitable for insert and delete on demand, avoiding waste of space and not suitable for query and modification

two。 structure

A linked list can actually be thought of as a rope with some knots.

In fact, a linked list is made up of nodes, but each node generally has two fields.

Value field data: data is stored in it

Next domain: what is stored is the address of the next node (is a reference variable)

Among them

Tail node: when the next domain of this node is null, this node is the tail node.

Header node: the first node of the whole linked list is the header node.

In practice, there are many linked list structures, and there are 8 kinds of linked list structures through the combination of the following situations (for example, leading one-way circular linked list is one).

Unidirectional and bidirectional

Lead node, no lead

Node cycle, acyclic

As shown in the figure above, it is an one-way non-leading non-cyclic linked list.

Some people may wonder, isn't there a head node in the above picture? Then why is it a linked list without leading nodes? I will change the above picture example slightly to take the lead in the node.

I have another node in front of the original header node, and the data in the value field of this node is optional because it has no effect on it. And the header node in this is just a sign indicating that this node is the header of the linked list.

What's the difference between a linked list with a lead node and a linked list without a lead node?

No lead: the header node of this linked list may be changed

Change lead: the header node of this linked list will not change

What does a circular list look like? We can modify the above one-way non-leading acyclic linked list slightly.

The next domain of the tail node stores the address of the header node

We know that a node usually has two fields, but if it is a two-way linked list, there are three fields.

Value field data: data is stored in it

Next domain: what is stored is the address of the next node (is a reference variable)

Prev domain: it stores the address of the previous node (is a reference variable)

That's how we draw a two-way acyclic linked list without taking the lead.

Next, I will mainly introduce one-way non-leading non-cyclic linked lists and two-way non-leading non-cyclic linked lists, which often appear in the interview questions.

Second, one-way non-leading non-cyclic linked list 1. Concept and structure

Through the above illustration, we should have an understanding of the one-way non-leading acyclic linked list. So how do you implement it in the code?

We know that the linked list should be seen as a class, while the node itself can be abstracted as a class.

First of all, for the node class, the code can write this

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

The numerical range is defined first, followed by the next domain (written as above because next stores the address of the next node). At the beginning, we can know val, so we can write a constructor to initialize val, but it is impossible to know the next domain of this node at the beginning, so we do not initialize next.

If you create a Node object, you can write a

Node node = new Node (10)

That is, the numerical range of the header node is 10.

Then define the linked list class, and the code can be written like this

Public class MyLinkedList {public Node head;}

We define a header node, which is easy for us to find. For example, if I want to insert a header into the linked list, the header node of the linked list changes all the time. So the above code is written to identify the header node of a single linked list.

two。 Realization of linked list

Next, let's implement some operations of one-way non-leading acyclic linked list.

Print linked list

Public void display () {Node cur= this.head; while (curving null) {System.out.print (cur.val + ""); cur=cur.next;} System.out.println ();}

Find the length of the linked list

Public int size () {Node cur=this.head; int count=0; while (curving null) {count++; cur=cur.next;} return count;}

Find whether the value key is in a single linked list

Public boolean contains (int key) {Node cur=this.head; while (curving null) {if (key==cur.val) {return true;} cur=cur.next;} return false;}

Clear single linked list

Public void clear () {this.head.val=0; this.head.next=null;}

Head insertion method

Public void addFirst (int data) {Node node=new Node (data); if (head==null) {this.head=node;} else {node.next = this.head; this.head=node;}}

Tail insertion method

Public void addLast (int data) {Node node = new Node (data); if (this.head==null) {this.head=node;} else {Node cur = this.head; while (cur.next! = null) {cur = cur.next;} cur.next = node;}}

Find the precursor node through the subscript (the first node is subscript 0)

Public Node searchPrev (int index) {Node cur= this.head; int count=0; while (countdown indexMouse 1) {cur=cur.next; count++;} return cur;}

Insert at any location

Public void addIndex (int index, int data) {if (indexsize ()) {throw new RuntimeException ("index illegal");} if (index==0) {addFirst (data); return;} if (index==size ()) {addLast (data); return;} Node node = new Node (data); Node cur = searchPrev (index); node.next=cur.next; cur.next=node;}

Find the precursor node with the value key (the first node is subscript 0)

Public Node searchPrevNode (int key) {Node cur= this.head; while (cur.nextframes null) {if (cur.next.val==key) {return cur;} cur=cur.next;} return null;}

Delete the node whose value is key for the first time

Public void remove (int key) {if (this.head==null) {return;} if (key==this.head.val) {this.head=this.head.next; return;} Node node= searchPrevNode (key); if (node==null) {System.out.println ("No elements in the linked list");} else {node.next = node.next.next;}}

Delete all nodes that appear with a value of key

Public void removeAllKey (int key) {if (this.head==null) {return;} Node prev=this.head; Node cur=this.head.next; while (curving null) {if (cur.val==key) {cur=cur.next; prev.next=cur;} else {prev=cur; cur=cur.next }} if (this.head.val==key) {this.head=this.head.next;}} Thank you for your reading. The above is the content of "detailed introduction of JAVA single linked list". After the study of this article, I believe you have a deeper understanding of the detailed introduction of JAVA single linked list, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.