This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

The advantages of linked lists

The advantages of linked lists over arrays are:

  • Memory space is not necessarily continuous, can make full use of the computer’s memory, to achieve flexible memory dynamic management.
  • The list does not need to be sized at the time it is created, and its size can be extended indefinitely.
  • List inInsert and DeleteData, the time complexity (that is, the computational effort required to perform the algorithm) can be achievedO(1), which is much more efficient than array.

The disadvantages of linked lists over arrays are:

  • When a linked list accesses an element at any location, it needs to be accessed from scratch
  • You can’t access an element through a subscript value like an array. You need to access it from scratch until you find the corresponding element

Package list

Each element of a linked list consists of a node that stores the element itself and a reference to the next element. That is, each node has its own data and a pointer to the next node, next, which is null by default.

function LinkList() { function Node(data) { this.data = data; this.next = null; } this.head = null; this.length = 0; // Record the number of linked list nodes}Copy the code

Common operations for linked lists

  • append(element): Adds a new element to the end of the list
  • insert(position, element): Inserts a new element into a position in the list
  • get(position): Gets the element in the corresponding position
  • indexOf(element): returns the index of the element in the list. Returns -1 if there is no such element
  • update(position, data): Modifies the data value of an element ata location
  • removeAt(position): Removes an element from a location in the list
  • remove(data): Removes an element from the list
  • isEmpty(): Returns true if there are no elements in the list. Otherwise return false
  • size(): returns the number of elements in the list, similar to the length attribute of an array
  • toString(): Elements in the list are Node classes and need to be overriddentoStringMethod to output the value of the printed element.

1. Append (data) method

If you are adding the first node, you need to do one more step — put the head pointer to the first node. If the first node is not added, the pointer to the last node points to the newly created node.

If the current pointer to the next current. Next is not null, assign the next node’s pointer to current. Until current.next is null, the node in which the pointer is located is the last node in the list. Simply point the null pointer to the newly created node.

LinkList.prototype.append = function (data) {
    var newNode = new Node(data);
    if (this.length == 0) {
        this.head = newNode;
    } else {
        var current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
    this.length += 1;
}
Copy the code

Insert (position, data) method

Insert an element into a position. The position I passed in here must not be less than 0, so return false if it is less than 0, and the position I inserted must not be greater than the length of the list, in which case RETURN false. Next, there are two ways to insert elements:

The first method is to insert the element into the first node, that is, the value of position is 0. At this time, the pointer of the created node should be changed to point to the element pointed to by the original this.head, and then let this.head point to the newly created element.

Second, insert the element in the middle or at the end, i.e. 0 < position < this.length, finding the last node at the position to be inserted. Next = current.next, and then have the current node point to the newly created element current.next = newNode

LinkList.prototype.insert = function (position, data) {
    var newNode = new Node(data);
    if (position < 0 || position > this.length) return false;
    if (position === 0) {
        newNode.next = this.head;
        this.head = newNode;
    } else {
        var current = this.head;
        for (var i = 0; i < position - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
    }
    this.length += 1;
}
Copy the code

3. The get method (position)

Get an element from a location, find the location, set current to the current location, and return the data value for the current location.

LinkList.prototype.get = function (position) {
    if (position < 0 || position >= this.length) return null;
    var current = this.head;
    for (var i = 0; i < position; i++) {
        current = current.next;
    }
    return current.data;
}
Copy the code

Update (position, data) method

Modifies the value of an element at a location. This is basically the same thing as get, except get just gets the data value for this location, whereas update tells us to change the data value to the data that was passed in. I don’t need to render this in code.

5. indexOf(element)methods

To look up the value (data) of an element in a linked list, and when the element is found, its index number (i.e., its location) is used. If this data is not found, it will return -1. Traverse the list, comparing each element’s data to the element you are looking for, and returning its index if the same.

LinkList.prototype.indexOf = function (element) {
    var current = this.head;
    var index = 0;
    while (current) {
        if (current.data == element) {
            return index;
        }
        current = current.next;
        index += 1;
    }
    return -1;
}
Copy the code

6. removeAt(position)methods

Removes an element from a location. There are two cases:

1) Delete element from position = 0; The deleted element still points to the second element, but no one points to it, so the browser automatically recycles the useless object.

2) Delete element from position > 0; Look for the element until the previous position of the element to be deleted, that is, current, current-. next originally pointed to the element to be deleted, and reassigned its point to current-.next, that is, to the element next to the element to be deleted. Finally, the data value of the deleted element is returned.

LinkList.prototype.removeAt = function (position) {
    var current = this.head;
    if (position < 0 || position >= this.length) return false;
    if (position == 0) {
        this.head = this.head.next
    } else {
        for (var i = 0; i < position - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    this.length -= 1;
    return current.data;
}
Copy the code

7. remove(data)methods

Remove elements whose data is equal to the passed data. 1) Use indexOf to obtain the position of data in the linked list; 2) Delete the node based on the location information and return the deleted data.

LinkList.prototype.remove = function (data) {
    var position = this.indexOf(data);
    return this.removeAt(position);
}
Copy the code

8. toString()methods

This method is just a way for us to look at the data in the list. Implementation method: traversing the list, the list of each node in the value of the value is removed into a string, and then returned as the return value,

LinkList.prototype.toString = function () {
    var current = this.head;
    var listString = '';
    while (current) {
        listString += current.data + ' ';
        current = current.next;
    }
    return listString;
}
Copy the code

\