a bit of linked list

As we have discussed, arrays are fixed in size as memories are allocated at compile time, which leads to possible wastage of memories due to excessive allocation. Hence, there is a desire to create a structure that can be flexible in terms of memory and yet provide the same functionality as arrays (which gives sequential representation of data). Such structures indeed exist, and one of the simplest implementation is called linked list.

As the name implies, linked list is a set of element linked to each other by a special relationship. Each element in a linked list has a value (called key) and a pointer to the element next to itself (called next). Hence, a linked list is constructed by artificially chaining an element to the next element until all elements are linked up with a parent-child relationship.

For example, if we want to represent {3,40,22,1} as a linked list, we will have 4 elements:
A {key=3,next=B}, B {key=40,next=C}, C {key=22,next=D} and D {key=1,next=NONE}. Hence we have a linked list of A->B->C->D. D is the end of the linked list, hence it does not point to any element, so we set its next to NONE.

The benefit of doing this is that when we want to insert element to the list, e.g. inserting E with key=90 after the last entry D, all we need to do is updating the pointer next of the last entry D to E, e.g. D {key=1,next=E}. Hence the new linked list is A->B->C->D->E.

On the other hand, if we are to add E in between B and C, we only need 2 changes:
1. instead of pointing to C, B will point to E
2. E should point to C.
e.g., set B to {key=40,next=E}, and set E {key=90,next=C}, hence we have a linked list of A->B->E->C->D.

Linked list also support deletion of an element, also by manipulating the pointers as we did in insertion. A simple implementation of deletion and insertion will be demonstrated in the codes provided below.

/* Linked List Simple Implementation */
struct node{
  int key;
  node* next;
};

class llist{
public:
  node* head; //starting point
  node* tail; //ending signal

  llist(){
    head=new node();tail=new node();
    head->next=tail; //initially, head points to tail(empty linked list)
    tail->next=tail; //tail points to itself
  }

  void del_next(node* n){
    node* t=n->next;
    n->next=t->next;
    delete t;  //freeing up memory
  }

  node* ins_next(node* n,int value){
    node* t=new node();
    t->key=value;
    t->next=n->next;
    return n->next=t; // returning "iterator" to last entry
  }
};

Notice that in its implementation, we need to provide 2 dummy elements, called head and tail, which signals the start and the end of a linked list. head will point to the first element of the linked list, while tail will be pointed by the last element of the linked list, with tail pointing to itself. Hence it will look like this: head->A->B->C->D->E->tail->(self-pointing).

You can extend this data structure to support more functionalities such as retrieving a pointer to a particular key, accessing an element through "index", sorting, and many more if you are interested.

Another interesting implementation of linked list is through array manipulation. While it may defeat the purpose of providing a structure with dynamic memory allocation, it allows us to understand the inner processes of linking elements. The implementation is very simple without the use of pointers (explicitly). We maintain 2 sets of arrays, one called key and another called next. Here is an example of the implementation:

#define MS 1000
int key[MS];
int next[MS];
int size,head,tail;

void link_init(){
  head=0;tail=1;size=2;
  next[head]=tail;
  next[tail]=tail;
}

void del_next(int node){
  next[node]=next[next[node]];
}

int ins_next(int node, int value){
  key[size]=value;
  next[size]=next[node];
  next[node]=size;
  return size++;

}

In this implementation, when we delete an element, it is not the element that is deleted, but rather its access that is discarded. This results in a very fast deletion and insertion operation on linked list. However, poor implementation of linked list may result in patches of memories becoming inaccessible and unavailable for future uses.