Linked List

Hello, fellow programmers!

I'm sure most of you must've heard about Array before, don't you?

Well today we'll be talking about something similar but slightly different, it's called Linked List.

What is Linked List?

If I were to associate it with things, I'll say linked list is sort of like a ton of numbered & locked box, where each box contains an item and a key to the next box. Formally speaking, Linked list is basically a collection, or a structure containing records of data, where each record contain the address or reference to the record next to it (sequencially).

There are two kinds of Linked List, they are called Single Linked List and Double Linked List. As the name suggests, Single Linked List is linked list that contains only the 'address/key' of the box after it, while Double Linked List contains both before and after.

Meaning, if you accidentally missed the box you're looking for in Single Linked List, you can't go back and you must start over again. 

Example of Double Linked List:

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

  };

  struct tnode *head = 0;

  struct tnode *tail = 0;

There's also a variation of linked-list called Circular Linked List, but all there's to it is that the tail
here will point to the head, while in normal linked list it will result in NULL.

How to use Linked List?

In linked list, you cannot access the data directly with index as in array. You must make use of a method called malloc() [Memory Allocation] and some asterisks(*) [pointer].

Why Linked List?

There is two major advantages that Linked List possess compared to Array.
First one being Linked-list is dynamic and flexible in size, unlike Array whose size are to be defined and fixed, therefore Linked-list can utilize memory more efficiently than array.
Finally, it all comes down to how efficient it is when it comes to modify records in Linked list. Unlike array where you have to loop an array of [n] for n times, all you have to do is a few row of codes. 

Here's the example of insertion and deletion of record in double linked-list

1. Supposedly you were to add a data at the first index(head)

struct tnode *node =(struct tnode*) malloc(sizeof(struct tnode));

  node->value = x;

  node->next  = head;

  node->prev  = NULL;

  head->prev  = node;

  head = node;

2. Supposedly you were to delete a data at neither head nor tail

struct tnode *curr = head;

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *a   = curr;

  struct tnode *del = curr->next;

  struct tnode *b   = curr->next->next;

  a->next = b;

  b->prev = a;

  free(del);     ---------Free is a method used to 'delete'/free up the memory used

 Imagine performing those two operations on array, how long would it be?

That's it for the introduction to Linked List, hope you learned something !

Data Reference

https://www.google.com/url?sa=i&url=https%3A%2F%2Fdev.to%2Fswarup260%2Fdata-structures-algorithms-in-javascript-single-linked-list-part-1-3ghg&psig=AOvVaw2ZE3m5di1jvI95IYS7V07T&ust=1582731947459000&source=images&cd=vfe&ved=0CAMQjB1qFwoTCKCAr5KG7ecCFQAAAAAdAAAAABAY

BinusMaya powerpoint slides i and ii

https://www.geeksforgeeks.org/linked-list-vs-array/

https://www.youtube.com/watch?v=pBrz9HmjFOs