This is the 13th day of my participation in Gwen Challenge

What is a linked list

A linked list stores an ordered collection of elements, but unlike an array, the elements in a linked list are not placed consecutively in memory. Each element consists of a node that stores the element itself and a reference (also known as a pointer or link) to the next element. As shown below:

  • One advantage of linked lists over traditional arrays is that you don’t need to move other elements when you add or remove them.
  • Linked lists require the use of Pointers, so the implementation of linked lists requires additional main.
  • When you want to access an element in the middle of the list, you iterate through the list from the starting point (the header) until you find the desired element.

A linked list is similar to a train structure in that each car is connected to each other, making it easy to separate a car, change its position, add or remove it.

Create a list

Implement the LinkedList class. The LinkedList data structure requires a Node helper class that represents the items to be added to the list. It contains an elemengt attribute, which is the value to add to the list, and a next attribute, which is a pointer to the next node item in the list. The LikedList class also has a Length attribute (an internal private variable) that stores the number of lists. In addition, we need to store a reference to the first node, which can be stored in a HEAD variable. The methods required for linked lists are as follows:

  • Append (Element): Adds a new item to the end of the list.
  • Insert (position, element): Inserts a new item into a specific position in the list.
  • Remove (element): Removes an item from a list.
  • IndexOf (element): returns the indexOf an element in a list. Returns -1 if the element is not in the list
  • RemoveAt (position): Removes an item from a specific position in the list.
  • IsEmpty (): Returns true if the list contains no elements, false if the length of the list is greater than zero
  • Size (): Returns the number of elements contained in the list, similar to the length property of an array.
  • ToString (): Since the list item uses the Node class, we need to override the default toString method inherited from the JS object to print only the value of the element.

Implement adding elements to the end of the list

function LikedList () {
    / / the node class
    let Node = function (element) {
           this.element = element
           this.next = null
    }
    // List number
    let length = 0 
    // Reference to the first node
    let head = null
    
    // Add a new item to the end of the list
    this.append = function (element) {
        When an element is appended to the end, there are two cases: the list is empty, the first element is appended, or the list is not empty and elements are appended to it
        let node = new Node(element)
        let current = null;
        if (head === null) {
            head = node
        } else {
            current = node
            // Loop through the list until the last item is found
            while(current.next) {
                current = current.next
            }
            // Find the last item and assign its next value to node to establish the connection
            current.next = node
        }
        length++
    }
    
    // this.insert = function (position, element) {}
    // this.removeAt = function (position) {}
    // this.remove = function (element) {}
    // this.indexOf = function (element) {}
    // this.isEmpty = function () {}
    // this.size = function () {}
    // this.getHead = function () {}
    // this.toString = function () {}
    // this.print = function () {}
}
Copy the code

PS: The next element of the last node in the list is always null

In the above code, the implementation steps are as follows:

  1. First pass element as a value to create the Node item. And record the current
  2. When creating a LinkedList object, head will point to null. If head is null, we are adding the first element to the list. All we need to do is assign the node created in the previous step to head
  3. When head is not empty, to add an element to the end of the list, the last element must be found first.
  4. Loop through the list until the last item is found, at which point we first make a current variable to represent the current item of the loop, starting with head, which means we start the loop at the beginning.
  5. If current. Next is not nul, it is not the last element, so assign current. Next to current, loop current to the next item.
  6. If current. Next is null, the last item (current) has been found, and the value of current. Next points to the node element to be added.
  7. By the end of step 6, we’ve added Node to the end of the list, but don’t forget to update the length
  8. Perfect finish.

To be continued… The next update removes elements from the linked list