MYF

[RA] Ch21 Linked Lists

Posted on | In | | Visitors

Reading Assignment: All of Programming Chapter 21 Linked Lists

Linked list is a data structure which is a linear sequence of nodes connected by pointers.

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
class LinkedList {
 class Node{
  public: 
   T data;
   Node * next;
 };
 Node * head;
 public:
  LinkedList():head(NULL){}
};

There are a few interesting things to note about this class declaration.

First, the inner class Node has a field which is a pointer to a node-the type is recursively defined: a Node has a pointer to a Node. As with recursive algorithms, recursive data-types are fine as long as they are well-founded. For types in C and C++, the compiler requires that until a type is fully declared, only pointers to that type may be used. This requirement ensures that all recursively defined types are well-founded and take finite space.

There are some common variations on the basic linked list structure. The variation we saw is a singly linked list, meaning that each node points only at the next element. An alternative is a doubly linked list, in which each node points not only at the next element, but also at the previous element. The advantage of a doubly linked list is that it makes traversing the list in the reverse direction much easier.

ADT for doubly linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
class LinkedList {
 class Node {
  public:
   T data;
   Node * next;
   Node * prev;
 };
 
 Node * head;
 Node * tail;
 size_t size;
public:
 LinkedList():head(NULL), tail(NULL)m size(0){}
};

It is also possible to make a circular list, in which there is no last node, but instead, the nodes form a circle.

Linked List Basic Operations

Add to Front

If we want to add an element to linked list, adding to the front is the easiest place to do so.

Two examples are given by video: One is singly linked list, another is doubly linked list.

Singly Linked list version:

1
2
3
4
void addFront(int data){
  head = new Node(data, head);
  size++;
}

Doubly Linked list version:

1
2
3
4
5
6
7
8
9
10
void addFront (int data) {
  head = new Node(data, head);
  if (tail == NULL) {
    tail = head;
  }
  else {
    head->next->prev = head;
  }
  size++;
}

Add to Back

If our list has a tail pointer, we can just use the tail pointer to find the last node. Otherwise, we must iterate through the nodes in the list, looking for one whose next field is NULL.

1
2
3
4
5
6
7
8
9
10
void addBack(int data){
  tail = new Node(data, NULL, tail);
  if (head == NULL) {
    head = tail;
  }
  else {
    tail->prev->next = tail;
  }
  size++;
}

Searching

time complexity: O(n)

Copying

If we want to make a deep copy of a linked list, we need to iterate through its nodes, creating new nodes with the same data, and linking them together so that the items appear in the same order. One way to do this would be to iterate through our source list in reverse order, and add each item to the front of the destination list.

Destruction

We need to use a temporary variable to remember the next node in the list, delete the current node, then go to the next node.

1
2
3
4
5
6
7
~LinkedList() {
  while (head != NULL) {
    Node * temp = head->next;
    delete head;
    head = temp;
  }
}

Insert in Sorted Order

Pointer to Node Before

One common approach to inserting in a particular position in a linked list is to search through the list for the node before where we want to add. That is, we have a Node * current and iterate through our list looking for the situation where we want to set current‘s next to the node we want to add.

Such an approach has a corner case when we want to add to the front of the list. 

1
2
3
4
5
6
7
8
9
10
11
12
void addSorted(const T & data) {
  if (head == NULL || data < head->data){
    head = new Node(data, head);
  }
  else{
    Node * curr = head;
    while (curr->next != NULL && data < curr->next->data){
      curr = curr->next;
    }
    curr->next = new Node(data, curr->next);
  }
}

Recursion

As linked list have recursive structure(Nodes have pointers to Nodes), they lend themselves quite naturally to recursive algorithm. Such algorithms typically take a Node * as a parameter, and have a recursive case on current->next. For operations which modify the structure of the list, these algorithms typically return a Node * which points at the resulting sequence of nodes, the method then update current based on this.

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
template<typename T>
class LinkedList {
 // other parts elided
private:
 class Node {
  public:
   T data;
   Node * next;
   Node(const T & d) : data(d), next(NULL) {}
   Node(const T & d, Node * n) : data(d), next(n){}
 };
 
 Node * addSorted(const T & data, Node * current){
   // base case: insert before current
   if (current == NULL || data < current->data) {
     return new Node(data, current);
   }
   // recursive case: add to the rest of list
   // then update current's next
   current->next = addSorted(data, current->next);
   return current;
 }
public:
 // has private recursive helper to do the work
 void addSorted(const T & data) {
  head = addSorted(data, head);
 }
}

Pointer-to-a-pointer

We can have a much more elegant iterative approach by recognizing the similarity between the two-they are both Node * s-and finding a way to deal with them uniformly. In particular, we can have a Node ** which points at the box we might want to change-and then we can point it at either head or the next field of any node.

1
2
3
4
5
6
7
8
void addSorted(int dataToAdd) {
  Node ** current = &head;
  while(*current != NULL && (*current)->data < dataToAdd) {
    current = &(*current)->next;
  }
  *current = new Node(dataToAdd, *current);
  size++;
}

Removing from a List

Remove from Front/Back

Removing from the head of a linked list can always be done in $O(1)$ time. After checking that the list is not empty, we just need to store the current value of the head pointer in a temporary variable, update the head pointer to head->next, then delete the original head node.

If our list is doubly linked, we need to update the prev pointer of new head node if the list is not empty. Likewise, if our list has a tail pointer, we need to check to see if it now empty, and if so, update the tail pointer to NULL.

Other Removals: Pointer to Node Before

As with inserting in the middle of the list, we can remove from the middle of the list by finding the node before the one we want to remove.

Once we have a pointer to the node before the one we want to remove, we first need to store the pointer to the node we want to delete, that is current->next in a temporary variable, so we can delete it later. We then need to update current-next to be current->next->next, which removes the desired node from the list.

Other Removals: Recursion

Here, we have two base cases:

  • If the current node is NULL, the list does not contain the item we are trying to delete, so we can just return the list unchanged, that is return NULL.
  • If the current node meets our criteria for deletion, we can remove the item from the list by returning everything after it, although we need to first delete the node we are removing.
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
template<typename T>
class LinkedList {
 // other parts elided
private:
 class Node {
  public:
   T data;
   Node * next;
   Node(const T & d) : data(d), next(NULL) {}
   Node(const T & d, Node * n) : data(d), next(n){}
 };
 Node * remove(const T & data, Node * current) {
   if (current == NULL) { // base case: empty list
     return NULL; // answer is empty list
   }
   if(data == current->data) { // base case node to remove
     Node * ans = current->next; // answer will be "everything after"
     delete current; // delete node we are removing
     return ans; // return our answer
   }
   
   // recursive case: remove from rest of list
   // then update current's next
   current->next = remove(data, current->next);
   return current;
 }
 public:
 // public remove method: just takes data to remove,
 // has private recursive helper do the work
 void remove(const T & data) {
   head = remove(data, head);
 }
}

Other Removals: Pointer-to-a-pointer

As with inserting, this gives us an elegant iterative approach because we no longer have a corner case for removing the head. We can keep a Node ** which starts at &head and represents the box we might want to change, then iterate along our list, trying to find the proper place from which to remove. Once we find it, we perform the appropriate pointer manipulations.

Remove All Occurrences

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
template<typename T>
class LinkedList {
  // other parts elided
 private:
  // private recursive helper
  
  // templated over whether to remove all or one
  template<bool removeAll>
  Node * remove(const T & data, Node * current){
    if(current == NULL) {
      return NULL;
    }
    if(data == current->data){
      Node * ans;
      if(removeAll) {
        ans = remove<removeAll>(data, current->next);
      }
      else{
        ans = current->next;
      }
      delete current;
      return ans;
    }
    current->next = remove<removeAll>(data, current->next);
    return current;
  }
 public:
 //public remove methods: just takes data to remove,
 // has private recursive helper do the work
 void remove(const T &data) {
   head = remove<false>(data, head);
 }
 void removeAll(const T & data) {
   head = remove<true>(data, head);
 }
};

Here, we have templated our private remove helper method over whether or not it should remove all elements(true) or just one(false). Recall that we can template over values as well as over types. Now, we have one copy of the code to do the work for removal, with a single if statement that choose whether to recurse or not. Our public methods then simply instantiate the remove template with either false or true as appropriate, and call it.

Iterators

Iterators are objects which encapsulate a position in a data structure, and give us a way to access and move through the elements without knowing the internal of that structure.

Implementation

We can implement the iterator by writing an inner class inside of our LinkedList class. As an inner class of linked list, the iterator is a part of the LinkedList class, and therefore it is fine for it to know about the implementation details of the list.

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
template<typename T>
class LinkedList {
 class Node {
  // contents of Node elided
 };
 
 public:
  class iterator {
      Node * current;
    public:
      class iterator {
        Node * current;
        public:
          iterator():current(NULL){}
          explicit iterator(Node *c):current(c){}
          iterator & operator++(){
            current = current->next;
            return *this;
          }
          iterator & operator++(){
           current = current->next;
           return *this;
          }
          iterator & operator++(int){
           iterator ans(current);
           current = current->next;
           return ans;
          }
          T & operator*() const{
            return current->data;
          }
          T * operator->()const{
            return &current->data;
          }
          bool operator != (const iterator &rhs) const {
            return current != rhs.current;
          }
          bool operator==(const iterator &rhs) const{
            return current == rhs.current;
          }
      }
  };
  
  class const_iterator{
    // similar, but const Node *
    // returns const &s/const *s
  };
  
  iterator begin(){
    return iterator(head);
  }
  
  iterator end() {
    return iterator(NULL);
  }
  
  const_iterator begin(){
    return const_iterator(head);
  }
  
  const_iterator end() {
    return const_iterator(NULL);
  }
};

Uses for ADTs

Stacks

We can both add to and remove from the front in $O(1)$ time, which is the best $O$ we can hope for. One downside of a linked list implementation is that we have a bit of space overhear(for every element, we store the element, as well as a next pointer).

Queues

We can implement both of insertion and removal in $O(1)$ time.

Sets

If we want a Set that is efficient for large $N$, we can use either a binary search tree or a hash table.

Maps