Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how to apply linked lists of JavaScript data structures". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The concept of linked list

Linked list is a common data structure. It is a structure that allocates storage dynamically. The linked list has a "head pointer" variable, represented by head, which holds an address that points to an element. Each node uses a reference indicator of an object, its successor, and a reference to another node is called a chain.

Array elements are referenced by subscripts (locations), while linked list elements are referenced by relationships with each other. Therefore, the insertion efficiency of the linked list is very high. The following figure shows the insertion process of the linked list node d:

Delete process:

Object-based linked list

We define two classes, the Node class and the LinkedList class, Node is the node data, and LinkedList saves the method of operating the linked list.

First, take a look at the Node class:

Function Node (element) {this.element = element; this.next = null;}

Element is used to save the data on the node, and next is used to save the link to the node.

LinkedList class:

Function LinkedList () {this.head = new Node ('head'); this.find = find; this.insert = insert; this.remove = remove; this.show = show;}

The find () method starts from the header node and searches along the list node until it finds an element equal to the item content and returns that node. If it doesn't find it, it returns empty.

Function find (item) {var currentNode = this.head;// starts from the header node while (currentNode. Elementaccountable item) {currentNode = currentNode.next;} return currentNode;// finds the returned node data, but does not find the return null}

Insert method. As you can see from the demonstration of the previous element insertion, there are four simple steps to implement the insertion:

1. Create a node

2. Find the target node

3. Modify the next of the destination node to point to the link

4. Assign the next value of the target node to the next of the node to be inserted

Function insert (newElement,item) {var newNode = newNode (newElement); var currentNode = this.find (item); newNode.next = currentNode.next; currentNode.next = newNode;}

The Remove () method. To delete a node, you need to find the previous node of the deleted node. For this reason, we define the method frontNode ():

Function frontNode (item) {var currentNode = this.head; while (currentNode.next.elementobitemps currentNode.NextNode.NextNode.n

Briefly answer three steps:

1. Create a node

2. Find the front node of the target node

3. The next of the node before modification points to the last node of the deleted node.

Function remove (item) {var frontNode = this.frontNode (item); / / console.log (frontNode.element); frontNode.next = frontNode.next.next;}

Show () method:

Function show () {var currentNode = this.head,result; while (currentNode.nextnodes null) {result + = currentNode.next.element;// in order not to display the head node currentNode = currentNode.next;}}

Test program:

Var list = new LinkedList (); list.insert ("a", "head"); list.insert ("b", "a"); list.insert ("c", "b"); console.log (list.show ()); list.remove ("b"); console.log (list.show ())

Output:

Bidirectional linked list

It's easy to traverse from the head node of the linked list to the tail node, but sometimes we need to go back and forward. At this point, we can add an attribute to the Node object that stores the link to the precursor node.

First, let's add the front attribute to the Node class:

Function Node (element) {this.element = element; this.next = null; this.front = null;}

Of course, we also need to modify the corresponding insert () method and remove () method:

Function insert (newElement,item) {var newNode = newNode (newElement); var currentNode = this.find (item); newNode.next = currentNode.next; newNode.front = currentNode;// add front to the precursor node currentNode.next = newNode;} function remove (item) {var currentNode = this.find (item); / / find the node if (currentNode.next! = null) {currentNode.front.next = currentNode.next that needs to be deleted / / Let the precursor node point to the next node of the node to be deleted currentNode.next.front = currentNode.front;// let the successor node point to the previous node of the node to be deleted currentNode.next = null;// and set the leading and subsequent directions to empty currentNode.front = null;}}

Display the linked list in reverse order:

You need to add a method to the two-way linked list to find the last node. The findLast () method finds the last node in the linked list, eliminating the need to traverse the chain from going back.

Function findLast () {/ / find the last node of the linked list var currentNode = this.head; while (currentNode.next! = null) {currentNode = currentNode.next;} return currentNode;}

Implement reverse output:

Function showReverse () {var currentNode = this.head, result = ""; currentNode = this.findLast (); while (currentNode.frontnodes null) {result + = currentNode.element + ""; currentNode = currentNode.front;} return result;}

Test program:

Var list = new LinkedList (); list.insert ("a", "head"); list.insert ("b", "a"); list.insert ("c", "b"); console.log (list); list.remove ("b"); console.log (list.show ()); console.log (list.showReverse ())

Output:

Cyclic linked list

A circular linked list is another form of linked storage structure. It is characterized by that the pointer domain of the last node in the table points to the head node, and the whole linked list forms a ring. Circular linked lists are similar to unidirectional linked lists, with the same node type. The only difference is that when you create a circular linked list, the next attribute of its header node points to itself, that is:

Head.next = head

This behavior is passed to each node in the linked list so that the next attribute of each node points to the header node of the linked list.

Modify the construction method:

Function LinkedList () {this.head = new Node ('head'); / / initialization this.head.next = this.head;// directs the next of the header node directly to the header node to form a circular linked list this.find = find; this.frontNode = frontNode; this.insert = insert; this.remove = remove; this.show = show;}

At this point, you need to pay attention to the output methods of the linked list, show () and find (). The original method will fall into a dead loop in the circular linked list, and the loop condition of the while loop needs to be modified to exit the loop when the loop reaches the header node.

Function find (item) {var currentNode = this.head;// starts from the header node while (currentNode.elementstarting itemized currentNode.next.elementstarting while) {currentNode = currentNode.next;} return currentNode;// finds the return node data, but does not find the return null} node () {var currentNode = this.head,result = "" While (currentNode.next! = null & & currentNode.next.element! = "head") {result + = currentNode.next.element + ""; currentNode = currentNode.next;} return result;}

Test program:

Var list = new LinkedList (); list.insert ("a", "head"); list.insert ("b", "a"); list.insert ("c", "b"); console.log (list.show ()); list.remove ("b"); console.log (list.show ())

Test results:

This is the end of the content of "how to apply the linked list of JavaScript data structures". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.