*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.