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

This article mainly introduces the JavaScript linked list how to achieve stack and queue related knowledge, the content is detailed and easy to understand, the operation is simple and fast, has a certain reference value, I believe that after reading this JavaScript linked list how to achieve stack and queue articles will have a harvest, let's take a look.

The time complexity of the linked list is as follows:

API description complexity add (index, e) insert operation O (n) remove (index, e) delete operation O (n) set (index, e) modify operation O (n) get (index, e) search operation O (n) contains (index, e) also search operation O (n)

This seems to show that the linked list is a data structure with poor performance. Let's make some adjustments to the interface of the linked list, and then take a look at the time complexity.

Interface description complexity addFirst (index, e) insert header operation O (1) addLase (index, e) insert chain tail operation O (1) removeFirst (index, e) delete header operation O (1) removeLast (index, e) delete chain tail operation O (1) getFirst (index, e) find chain header operation O (1)

After adding these interfaces, the complexity of the linked list becomes O (1).

Linked list implementation stack

Linked list implementation queue

According to the nature of the queue, the operation of the queue is bound to affect both ends of the linked list. According to the previous table, we can know that one end is O (1) and the other end is O (n).

Why the operation of the linked header in the linked list is simply O (1)? as can be seen from the above figure, because there is an identification bit head, the header can be quickly positioned. Similarly, we can set a tail variable, which is easy to insert elements at both ends.

In this way, the queue removes the element from the head end and inserts the element from the tail side.

The head of the head team is responsible for leaving the team and the end of the tail team is responsible for joining the team.

This is the end of the article on "how JavaScript linked lists implement stacks and queues". Thank you for reading! I believe that everyone has a certain understanding of "JavaScript linked list how to achieve stack and queue" knowledge, if you want to learn more knowledge, 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.