Linked List

Created by ThangVu

Definition

A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.

Fig. 1. The illustration of a linked list with 3 elements. 

Linked list is a simple and common data structure. They can be used to implement other data types, such as stacks, queues, associative arrays, S-expression. 

Advantages 

• Linked lists are a dynamic data structure, which can grow and be pruned while the program is running.
• Insertion and deletion node operations are easily implemented in a linked list
• Linear data structures such as stacks and queues are easily executed with a linked list
• They can reduce access time and may expand in real-time without memory overhead

Disadvantages

• They use more memory than arrays because of the storage used by their pointers
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache
• Difficulties arise in linked lists when it comes to reverse traversing. 

There are two common type of linked list: singly linked list and double link list. A singly linked list is illustrated in Fig.1. A doubly linked list is described in Fig.2, in this case we need two pointers to store addresses of the previous node and the next node.

Fig. 2. The illustration of a doubly linked list.

Implementation of linked list

In this post, i will present how to implement a singly linked list in C programming language (structure, basic functions and examples).
First, we declare a struct representing a node of linked list:

/* struct node represent an element of linked list */
struct node_s {
 int data;
 struct node_s* next_node;
};
typedef struct node_s node_t;

The struct consists of an integer number and a pointer storing the address of the next node.

We have two global variables: the length of the linked list and the head node that store the address of the first node of the linked list.

int list_len = 0;
node_t *head = NULL;

Now, we declare some basic function:

/* function name : create_node
 * Description     : create a new node based on passed integer value, return created node*/
node_t *create_node(int num) {
 node_t *node = (node_t*) malloc(sizeof(node_t));
 node->data = num;
 return node;
}

Function create_node allocates a new memory for a new node, assigns passed integer number to its data and return the created node.
__________________________________________________________________________

/* function name : is empty
 * Description     : check the linked list is empty or not*/
int is_empty() {
 if (head == NULL) {
  return 1;
 }
 return 0;
}

This function check if the linked list is empty or not by checking the head node.
___________________________________________________________________________

/* function name : get_node_at_index
 * Description     : get a node at a index of the linked list*/
node_t *get_node_at_index(int index) {
 if (index < 0 || index > list_len - 1) {
  printf("Index must be in range of [0, %d].\n", list_len - 1);
  return NULL;
 } else {
  int i;
  node_t *temp = head;
  for (i = 0; i < index; i++) {
   temp = temp->next_node;
  }
  return temp;
 }
}

Function get_node_at_index check if the index is valid or not, then transfer through the head node to the index and return the node found node. The function return NULL if the index is out of the list scope.
___________________________________________________________________________

/* function name : insert_at_begin
 * Description     : insert a node at the beginning of the linked list and update linked list length*/
void insert_at_begin(node_t *node) {
 if (head == NULL) {
  head = node;
 } else {
  node->next_node = head->next_node;
  head->next_node = node;
 }
 list_len++;
 printf("Insert %d at begin!\n", node->data);
}

Function insert_at_begin inserts a node at the beginning of the linked list and update its length.
____________________________________________________________________________

/* function name : insert_at_index
 * Description     : insert a node at a index (in range of [0, list_len]) of the linked list and update linked list length */
void insert_at_index(int index, node_t *node) {
 if (index == 0) { /*exception at index 0 */
  insert_at_begin(node);
 } else {
  node_t *node_of_index = get_node_at_index(index - 1); /* adj_node stores the index to be inserted*/
  if (node_of_index != NULL) {
   node->next_node = node_of_index->next_node;
   node_of_index->next_node = node;
   printf("Insert %d at index %d!\n", node->data, index);
   list_len++;
  }
 }
}

Function insert_at_index gets the node corresponding to the index (adjacent node), then insert a new node after this node.
____________________________________________________________________________

/* function name : delete_at_index
 * Description     : delete a node at a index (in range of [0, list_len - 1]) of the linked list and update linked list length */
void delete_at_index(int index) {
 node_t *deleted_node;
 if (index == 0) {/*exception at index 0 */
  if (list_len == 0) {
   printf("Invalid index");
  } else {
   deleted_node = head;
   head = head->next_node;
   free(deleted_node);
   printf("Delete node at index %d\n", index);
   list_len--;
  }

 } else {
  node_t *node_of_index = get_node_at_index(index - 1);
  if (node_of_index != NULL) {
   deleted_node = node_of_index->next_node;
   node_of_index->next_node = deleted_node->next_node;
   free(deleted_node);
   printf("Delete node at index %d\n", index);
   list_len--;
  }
 }

}

Function delete_at_index find the adjacent node (as in the insert_at_index function) then delete the node corresponding to the index.

/* function name : delete_all
 * Description     : deleted all element in linked list */
void delete_all() {
 node_t *temp;
 while (!is_empty()) {
  temp = head;
  head = temp->next_node;
  free(temp);
 }
 list_len = 0;
 printf("delete all elements!\n");
}

Function delete_all deletes each node of the linked list until the list is empty.

/* Function name : print_list
 * Description  : print all elements of the linked list */
void print_list() {
 node_t *temp = head;
 printf("Linked list is: ");
 if (is_empty()) {
  printf("empty");
 } else {
  while (temp != NULL) {
   printf("%d\t", temp->data);
   temp = temp->next_node;
  }
 }

 printf("\n-------------------------------\n");
}

Function print_list print out the data of the link list.
______________________________________________________________

int main(void) {
 //head = (node_t*) malloc(sizeof(node_t));
 int arr[5] = { 1, 3, 6, 4, 7 };
 int i;
 print_list();

 /* Insert at begin and print link list */
 for (i = 0; i < 5; i++) {
  node_t *new_node = create_node(arr[i]);
  insert_at_begin(new_node);
 }
 print_list();

 /*Insert at a index and print link list*/
 node_t *new_node = create_node(10);
 insert_at_index(3, new_node);
 print_list();

 /* Deleted node at a index and print link list*/
 delete_at_index(2);
 print_list();

 /* Deleted all */
 delete_all();
 print_list();

 return EXIT_SUCCESS;
}

In main function, we test following features:

• Insert an integer array (1, 3, 6, 4, 7) in turn to the beginning of the linked list.
• Insert a node (data = 10) to index #3 of the linked list
• Delete node #2 of the linked list.
• Clear the linked list.

Output:

Linked list is: empty
-------------------------------
Insert 1 at begin!
Insert 3 at begin!
Insert 6 at begin!
Insert 4 at begin!
Insert 7 at begin!
Linked list is: 1 7 4 6 3 
-------------------------------
Insert 10 at index 3!
Linked list is: 1 7 4 10 6 3 
-------------------------------
delete 4 at index 2!
Linked list is: 1 7 10 6 3 
-------------------------------
delete all elements!
Linked list is: empty
-------------------------------

Example of the above linked list is available at here.

Reference:
https://en.wikipedia.org/wiki/Linked_list
http://www.tutorialspoint.com/data_structures_algorithms/linked_lists_algorithm.htm