Preface:
I am very grateful to every friend who cares about my second brother. With the help of friends, my second brother has learned a lot. I also hope to share the knowledge I have learned with every friend in need. If there are mistakes in the article, I hope you can point out more. Have better ideas, ideas can also leave a message or private chat me. I don’t appreciate it.
Brief introduction:
Linked list in the data structure, is a very basic and easy to understand a data structure. Each language has a slightly different implementation, but the general idea is the same. Today we introduce one-way linked lists. The difference between one-way and two-way linked lists is that there is no reference to a parent node.
The structure of the linked list consists of a root node containing two fields, a value for the current node and a reference to the next node. An array is very similar to a linked list, but the structure of an array is to create a space in memory that can be expanded or reduced depending on the length of its contents. Arrays are compact data structures. The storage of data by index is an ordered arrangement. Arrays have many more methods than linked lists and can do different things to the data.
A linked list is a chain of references in a heap of memory. It’s not ordered.
// List data structure [1, 2, 3]
let linkedList = {
value: 1.next: {
value: 2.next: {
value: 3.next: null}}}Copy the codeThere is no native list structure provided in JavaScript. We can simulate a linked list in our own code. The linked list requires a head node (head), which is null by default. We want to add a node to the list, so we need a method to add a node, and we want to know if the list contains a node, delete a node and so on, and I’ll list some common methods.
- AddLast // Adds a node to the end
- AddFirst // Add a header node
- IsEmpty // determines whether the current list isEmpty
- Find // Finds the specified element
- FindLast // Get the last node
- RemoveLast removes the last node
- RemoveFirst // Remove the first node
- Remove // Deletes a specified node
- Insert // Insert at the specified location
- Dir // Expand the list
Now that we know what the list contains, we’re going to implement it one by one, first we need a list constructor, which becomes a container to hold our list and the corresponding methods.
class LinkedList{
constructor() {
// Add a length attribute
this.size = 0;
// Declare a header node
this.head = null;
// Maintain a tail node (handy when adding)
this.tail = null; }}Copy the codeNow that we have the basic structure of the linked list, we also need a node-generating constructor to help us build one node at a time.
class Node{
constructor( data ) {
// Value of the node
this.value = data;
// The next reference to the node points to
this.next = null; }}Copy the codeWe are almost ready now. We already have our linked list. But it is like designing a robot, but it has not designed its action instructions, and it can only look at it and not use it. So let’s start by adding a node.
Tail-add node. We reserved a reference to a tail-add node when we designed the linkedList, so that when the list is large, we don’t have to go through the list to add the last node, which is very fast, but it starts with null. Prove that there is no tail node yet. The root node doesn’t even exist yet, so in this method of adding nodes. What we need to do is determine if there is a root node, add it to the root node if there is a tail node, add it to the root node if there is no tail node, and maintain the tail node and update the list length.
addLast( item ) {
// Do a non-null validation of the argument
if ( !item ) { throw new Error('Please enter a correct node! ')}// Create a node
let node = new Node(item);
// Check whether the list is empty
if ( this.size === 0 ) {
// Update the tail node, update the head node
this.tail = this.head = node;
} else {
// Set a reference to the tail node
this.tail.next = node;
// Update the latest tail node to tail
this.tail = node
}
// Update the length
this.size++;
}
Copy the codeHaving just added a node to the end of the list, we can also add a node to the head. The idea is not that different, because we have a header node that we can get directly.
addFirst( item ) {
// Do a non-null validation of the argument
if ( !item ) { throw new Error('Please enter a correct node! ')}// Create a node
let node = new Node(item);
// Check whether the current list is empty
if ( this.size === 0 ) {
this.head = this.tail = node;
} else {
// Make the entire list a next reference to the new node
node.next = this.head;
// Assign node to head
this.head = node;
}
// Update the length
this.size++
}
Copy the codeAdding a node to the header is also implemented. Adding a node to the tail is also implemented. At this point we can implement the search method. The main function of the lookup method is to check whether the current linked list contains a node. If you need to implement a linked list without repeated nodes, you can also call the lookup method before each addition to see whether the added node exists. We don’t have similar restrictions here.
find( item ) {
// Do a non-null validation of the argument
if ( !item ) { throw new Error('Please enter a correct node! ')}// Get the entire node
let linkedList = this.head;
// loop judgment
while( linkedList && linkedList.next && linkedList.value ! == item ){ linkedList = linkedList.next; }return linkedList
}
Copy the codeWith add, find. Head deletion is relatively simple. Find the reference of the first head node and return it, and then point the head to the next reference of the head node to delete the head node.
removeFirst (){
// Define a return value
let res = null;
// Check that the current list is not empty
if ( this.size ! = =0 ) {
res = this.head;
// Skip the head node and point head to next of head
this.head = this.head.next;
res.next = null;
// Maintain the length
this.size--;
// Delete all references to the end node
this.tail = this.size ? this.tail : null;
} else {
// If the list is empty, the delete operation is called and a warning is issued
throw new Error('Linked list is empty and cannot be deleted! ')}return res
}
Copy the codeAfter deleting the header node is implemented, we can also delete the tail node. To delete the tail node, we need to traverse the parent of the tail node first, and then update the reference of the tail node.
removerLast() {
// Define a return value
let res = null;
// Get all nodes
let linkedList = this.head;
// Check whether the current list has only one node
if ( this.size === 1 ) {
res = this.head;
this.head = this.tail = null;
res.next = null;
}
// The list is empty
if ( this.size === 0 ) {
// If the list is empty, the delete operation is called and a warning is issued
throw new Error('Linked list is empty and cannot be deleted! ')}else {
// loop to find the penultimate node
while ( linkedList && linkedList.next && linkedList.next.next ){
linkedList = linkedList.next;
}
res = linkedList.next;
// Make the last reference null
linkedList.next = null;
// Maintain the tail node
this.tail = linkedList;
// Maintain the length
this.size--;
}
return res
}
Copy the codeWith the experience of the previous two deletion methods, let’s implement the deletion of the specified node. Deleting a specified node also requires traversing the linked list to obtain the parent of the specified element, similar to deleting the last node. Instead of determining whether the lower child is equal to the element specified for deletion. Since there is no restriction on uniqueness in the version we are sharing today, deletion defaults to the first element found.
remover( item ){
// Define a return value
let res = null;
// Do a non-null validation of the argument
if ( !item ) { throw new Error('Please enter a correct node! ')}// Get the entire list
let linkedList = this.head;
// Check that the list has only one node
if ( this.size === 1 && linkedList.value === item ) {
res = linkedList;
// Maintain the head and tail nodes
this.head = this.tail = null;
} else {
// Loop to find the parent of the specified node
while( linkedList && linkedList.next && linkedList.next.value ! == item ) { linkedList = linkedList.next; }// Check whether it exists
if ( linkedList && linkedList.next ) {
// Save the deleted node
res = linkedList.next;
// Delete the specified node
linkedList.next = linkedList.next.next;
} else {
throw new Error('This node is not in the linked list, cannot be deleted! ')}}// Determine whether the deleted node is the last node
this.tail = linkedList.next ? this.tail : null;
// Delete the next pointer of the node
res.next = null;
// Maintain it
this.size--;
return res
}
Copy the codeSometimes we need to check if the list isEmpty, so let’s implement isEmpty, which is kind of neat. Because we just need to look at the size property we’re maintaining to know if it’s empty. Although the list we’re building here can actually be found in the size property of the entire list. The null function is not needed. However, when used in real development, you don’t want the size attribute to be changed. And it won’t be exposed. JavaScript is more flexible, and many restrictions are not as easy to handle as Java. We didn’t try to limit it here.
isEmpty() {
return this.size === 0
}
Copy the codeNow our linked list actually does all the basic functions. Generally, the operation of a data is nothing more than adding, deleting, changing and checking. At present, we have realized it. You can also add an insert function, insert is specified to insert, if the location can not be found, throw error, if the location is correct, insert incorrect node also throw error.
insert ( item, ele ) {
// Verify that both parameters cannot be null
if(! item || ! ele ) {throw new Error('Please enter a correct node or find the element! ')}// Get the entire list
let linkedList = this.head;
// Loop to find matches
while( linkedList && linkedList.value ! == item ) { linkedList = linkedList.next; }// Check the result, the result can only be two, found, not found
if ( linkedList ) {
// Generate a node
let node = new Node(ele);
// Point the next reference of the matched node to the next reference of the new node
node.next = linkedList.next;
// Assign the new node to the matched node
linkedList.next = node;
// Determine if the last element was inserted
this.tail = node.next ? this.tail : node;
// Maintain the length
this.size++;
} else {
throw new Error('No element matches where it needs to be inserted! ')}}Copy the codeIn the usual will also pay attention to the first and last linked list item. In a bidirectionally linked list, you can traverse backwards or backwards. You have to go straight to the tail node, and we don’t have a two-way list in this example. But we maintain a tail node, so it’s easier to get the last item in the list.
findLast() {
return this.tail
}
Copy the codeBecause the structure of the whole linked list is more complex. It is not particularly convenient to view. At the beginning of the article, I briefly explained the structure of the expanded surface of three nodes. It’s not very good for reading. So if we had a list of 30 lengths, maybe the expansion would be very large. At this point we need a way to view the entire list.
dir(){
// Define a return value
let res = ' ';
// Get the entire list
let linkedList = this.head;
res = linkedList ? linkedList.value : ' ';
// Loop through the list
while ( linkedList.next ) {
res += '- >' + linkedList.next.value;
linkedList = linkedList.next;
}
// Return data
return res
}
Copy the codeLinked lists can do a lot of things. It’s a very nice data structure. For example, you can use linked lists to implement a tiny array in JavaScript, implement a stack, implement a queue. I’ll update a chapter on implementing a list as a miniature array later if I have time.
The introduction of linked lists and the implementation of some functions has ended, not very detailed, if there is a wrong place. Code specification, code logic error, hope you can give more advice.
As for the source code of the linked list introduced above, I put it on Gitee, originally intended to put it on Github, I don’t know why I can’t put it on today. I have also shared some problems on the link brush problem solution, today to share the linked list, I also find a link on the link of the middle problem to achieve. Those who are interested can go and have a look. thank you
Just got to Denver. Other historical articles shared in the public account, interested friends can pay attention to a wave of public account. In the future, we will update the public account and the nuggets public account simultaneously.
Gitee address: https://gitee.com/chengxinyingtianxia/leetcodeCopy the code