Linked Lists

2018-03-11

The linked list datat structure

  • Disadvantage of Array:
    • the size of array is fixed
    • inserting or removing items from the beginning or from the middle of the array is expensive, because the elements need to be shifted over.
  • Linked Lists
    • Linked lists store a sequential collection of elements; but unlike arrays, the elements are not placed contiguously in memory. Each element consists of a node that stores the element itself and also a reference that points to the next element.
    • advantage over conventional array: do not need to shift elements over when adding or removing them.
    • disadvantage over conventional array: if we want to access an element from the middle, we need to start from the beginning and iterate the list until we find the desired element.

Creating a linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function LinkedList(){
    let Node = function(element){
        this.element = element;
        this.next = null;
    };
    let length = 0;
    let head = null;

    this.append = function(element){};// This adds a new item to the end of the list
    this.insert = function(position, element){}; // This inserts a new item at a specified position in the list
    this.removeAt = function(position){}; // removes an item from a specified position in the list 
    this.remove = function(element){};// removes an item from the list
    this.indexOf = function(element){};// this returns the index of the element in the list, if the element is not in the list, it returs -1
    this.isEmpty = function(){};
    this.size = function(){};
    this.toString = function(){};
    this.print = function(){};
}
  • Appending elements to the end of the linked list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
this.append = function(element){
    let node = new Node(element), current;

    if( head === null ){
        head = node;
    } else {
        current = head;
        while(current.next){
            current = current.next;
        }
        current.next = node;
    }
    length ++;
}
  • Removing elements from the linked list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
this.removeAt = function(position){
    if(position > -1 && position < length){
        let current = head,
        previous,
        index = 0;
        if( position === 0 ){
            head = current.next;
        } else {
            while (index++ < position){
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        length --;
        return current.element;
    }else{
        return null;
    }
}

  • Inserting an element at any position

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    this.insert = function(position, element){
        if (position >= 0 && position <= length){
            let node = new Node(element), current = head, previous, index = 0;
            if (position === 0){
                node.next = current;
                head = node;
            } else {
                while ( index ++ < position ){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            length ++;
            return true;
        }else{
            return false;
        }

    }

  • The toString() method

    1
    2
    3
    4
    5
    6
    7
    8
    9
    this.toString = function(){
        let current = head,  string = '';

        while(current){
            string += current.element + (current.next ? 'n' : '');
            current = current.next;
        }
        return string;
    }

  • The indexOf method

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    this.indexOf = function(element){
        let current = head, index = -1;
        while ( current ){
            if ( element  === current.element){
                return index;
            }
            index ++;
            current = current.next;
        }
        return -1;
    }

  • The remove() method

    1
    2
    3
    4
    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    }

  • The isEmpty(), size(),and getHead() methods

    1
    2
    3
    4
    5
    6
    7
    8
    9
    this.isEmpty = function(){
        return length === 0;
    }
    this.size = function(){
        return length;
    }
    this.getHead = function(){
        return head;
    }

  • The final Version

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    function LinkedLists(){
        let head = null, length = 0;
        let Node = function(element){
            this.element = element;
            this.next = null;
        }
        this.append = function(element){
            let node = new Node(element), current;
            if(head === null){
                head = node;
            }else{
                while(current.next){
                    current = current.next;
                }
                current.next = node;
                length ++;
            }
        }
        this.insert = function(position, element){
            if (position > -1 && position < length){
                let node = new Node(element), current = head, previous;
                if (position === 0){
                    head = node;
                    node.next = current;
                } else {
                    let index = 0;
                    while(index ++ < position){
                        previous = current;
                        current = current.next;
                    }
                    previous.next = node;
                    node.next = current;
                }
                length ++;
                return true;
            }else{
                return false;
            }
        }
        this.removeAt = function(position){
            if (position > -1 && position < length){
                let  current = head, previous;
                if (position === 0){
                    head = current.next;
                    length --;
                    return current.element;
                } else {
                    let index = 0;
                    while (index ++ < position){
                        previous = current;
                        current = current.next;
                    }
                    previous.next = current.next;
                    length --;
                    return current.element;
                }
            } else {
                return null;
            }
        }
        this.indexOf = function(element){
            let current = head, index = -1;
            while(current){
                if(element === current.element){
                    return index;
                }else {
                    index ++;
                    current = current.next;
                }
            }
            return -1;
        }
        this.remove = function(element){
            let index = this.indexOf(element);
            return this.removeAt(index);
        }
        this.size = function(){
            return length;
        }
        this.isEmpty = function(){
            return length === 0;
        }
        this.toString = function(){
            let current = head, string = '';
            while(current){
                string += current.element;
                current = current.next;
            }
            return string;
        }
        this.print = function{
            console.log( this.toString());
        }
    }

Doubly linked lists

  • In the doubly linked list, we have a double link: one for the next element and one for the previous element.
  • Thus, it provides us with two ways to iterate the list: from the beginning to its end and vice versa.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function DoublyLinkedList(){
    let Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null;
    };
    let length = 0;
    let head = null;
    let tail = null;
}
``` 

- Inserting a new element at any positon

```javascript
this.insert = function(position, element){
    if(position >= 0 && position <= length){
        let node = new Node(element), previous, current = head, index = 0;
        if (position === 0){
            if(!head){
                head = node;
                tail = node;
            } else {
                node.next = current;
                current.prev = node;
                head = node;   
            }
        } else if (position === length ){
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        } else {
            while (index ++ < position){
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node;

            current.prev = node;
            node.prev = previous;
        }
        length ++;
        return true;
    } else {
        return false;
    }
}
  • Removing elements from any position.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    this.removeAt = function(position){
        if (position > -1 && position < length){
            let current = head, previous, index = 0;
            if (position === 0){
                head = current.next;

                if (length === 1){
                    tail = null;
                } else {
                    head.prev = null;
                }
            } else if ( position === length - 1){
                current = tail;
                tail = current.prev;
                tail.next = null;
            } else {
                while (index ++ < position){
                    previous = current
                    current = current.next;
                }
                previous.next = current.next;
                current.next.prev = previous;
            }
            length --;
            return current.element;
        } else {
            return null;
        }
    }

Circular Linked Lists

  • Circular Linked List: have one reference direction and its last element’s next pointer does not make reference to null, but to the first element - the head.
  • doubly circular linked list: have two reference direction and has tail.next pointing to the head element, and head.prev pointing to the tail element;