Analysis of the difference between array and linked list

Hello everyone , I meet you again , I'm your friend, Quan Jun .

1. What is a linked list

A linked list is a storage structure in which the reference of the previous element points to the next element , The linked list connects elements with elements through pointers ;

Linked list is a kind of linear list , The so-called linear list includes sequential linear list and linked list , Sequential linear table is realized by array , There is a sequential arrangement in memory , By changing the size of the array . The linked list is not implemented in order , Use a pointer to achieve , Discontinuous in memory . That is to say , Linked list is to connect a series of discontinuous memory , Make rational use of that fragmented memory , Solve the problem of space .

therefore , Linked list allows you to insert and delete nodes anywhere on the list , But random access is not allowed . There are many different types of lists ： One way linked list 、 Two way linked list and circular linked list .

2. One way linked list

The one-way linked list contains two fields , One is the information domain , One is the pointer field . That is, the nodes of the one-way linked list are divided into two parts , One part is to save or display information about the node , The second part stores the address of the next node , The last node points to a null value .

3. Double linked list

It's clear from the picture above that , Each node has 2 A link , One refers to the previous node （ When this link is the first link , Point to null value or empty list ）, The other one points to the latter node （ When this link is the last link , Point to null value or empty list ）. It means that the two-way linked list has 2 A pointer to the , One refers to the pointer to the previous node , The other is a pointer to the next node .

4. Circular linked list

Circular linked list is that the first node and the end node are connected . The first node in the circular linked list is the last node , vice versa .

5. The difference between arrays and linked lists ？

Different ： The linked list is linked Storage structure ; Arrays are sequential Storage structure .

The linked list connects elements with elements through pointers , An array stores all the elements in order .

The insertion and deletion elements of the linked list are relatively simple compared with the array , No need to move elements , And it is easy to realize length expansion , But finding an element is more difficult ;

It's easier to find an element in an array , But insertion and deletion are complex , Due to the maximum length, it needs to be specified at the beginning of programming , So when the maximum length is reached , The extended length is not as convenient as the linked list . identical ： Both structures can realize the sequential storage of data , The constructed model is Linear structure .

6. The application of linked list 、 Code practice

Joseph's question ：

It is said that in the park 1 In the Jewish War of the th century , Jewish Joseph is a famous historian in the first century AD . After the Romans took jotapat ,39 A Jew hid in a cave with Joseph and his friends ,39 A Jew decided that he would rather die than be captured by the enemy , So I decided to commit suicide through the ages ,41 Individuals in a circle , From the first 1 Individual starts counting , Every check-in day 3 You have to kill yourself , Then the next person will count off again , Until everyone killed himself . But Joseph and his friends didn't want to follow the agreement , Joseph asked his friend to pretend to obey , He arranged his friend and himself in the _ And the first _ A place , So I escaped the game of death , You know what's arranged in the first few ？

For the above problems , Use one-way circular linked list to solve ：

                        // Node class 
			function Node(elemnt) {
				this.item = elemnt;
				this.next = null;
			}
			// The circular list needs to modify the constructor , And the judgment conditions during traversal 
			// The constructor is as follows ; Hope to traverse from back to front , I don't want to establish a two-way linked list , Just use the circular linked list .
			function Llist() {
				this.head = new Node("1");
				this.head.next = this.head;
				this.remove = remove;
				this.insert = insert;
				this.find = find;
				this.display = display;
				//..........
			}
			function find(number) {
				var curr = this.head;
				while (curr.item != number) {
					curr = curr.next;
				}
				return curr;
			}
			function insert(element, newElement) {
				var preNode = this.find(element);
				var current = new Node(newElement);
				current.next = preNode.next;
				preNode.next = current;
			}
			function remove() {
				var current = this.head;
				console.log("remove");		
                       // Skip two , Kill one 
			while(current.next.next != null && current.item!=current.next.next.item){
					var temp = current.next.next;
					current.next.next = temp.next;
					current = temp.next;
					temp.next = null;
				}
				return current;
			}
			function display(flag,current) {
				var crr = this.head;				
				if(flag){
					while(crr.next.item!="1"){
						console.log(crr.item);
						crr=crr.next;
					}
				   }else{   // Finally, there are only two direct outputs 
					console.log(current.item);
					console.log(current.next.item);
				}
			}
			var Clist = new Llist();
                        // Enter sort 
			for (var i = 1; i < 41; i++){
				Clist.insert(i.toString(),(i + 1).toString());
			}
                        // Output all first 
			Clist.display(1,null);
                        // adopt remove Return one of the nodes after the last kill 
			Clist.display(0,Clist.remove());  //16,31

Copy

The way of organizing code should be learned ;

7. Self understanding

1） Arrays are easy to query and modify , However, it is inconvenient to add and delete

2） Linked lists are suitable for adding and deleting , But it is not suitable for query , Using appropriate data structures and algorithms according to business conditions is a problem that must be considered when there is a large amount of data and high concurrency

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/147716.html Link to the original text ：https://javaforall.cn