Understanding Linked List

Greeting fellow coder.

On this installment I will break down Linked List data structure...you will learn about the fundamentals, how they work, a variation called a "doubly linked list" (I didn't make that up), and ask the question... are they easy to learn and should you? spoiler...you should.

What is A Linked List ?

Linked List is a data structure consisting of a group of vertices (nodes) which together represent a sequence. Each vertex is composed of a data and a reference (link) to the next vertex in the sequence. In simpler terms, it is a flexible data structure that can store many nodes, and it does this by having each nodes point to the next node in the list.

Linked List and its variations are used as underlying data structure to implement List, Stack, Queue, and ADTs(Abstract Data Types).

breakdown:

1. This particular linked list there is 7 nodes, and in each node there is a specific variable in this case they are numbers [22,2,77,6,43,76,89]
2. The arrows for each nodes connecting one to another, these arrow are called pointers.
3. The "head" label indicates when the linked list begin and the 'tail' label indicates when it ends.
4. If you are looking at the tail node and wondering "hey isn't every node in a linked list suppose to have a pointer that points to the next node". You are 100% right, as a matter of fact the last node does have a next pointer value and it is 0 or null, which indicate you have reach the end of the list.

How do you use it?

Since Linked List is such a fundamental and simple linear data structure. It has a range of potential applications as a list ADT(Abstract Data Type) e.g. student list, event list, appointment list, etc.

As stated earlier Linked List is also being used as an underlying structure to create other more complex structure such as Queues and Stacks.

Furthermore because linked list can be easily be reorder, split, trimmed, reverse, and so on. They can be pretty useful for algorithm like sorting.

Lets try to search a value of 43 from the linked list example above

breakdown:

1. Searching through a linked list is fairly simple, the algorithm will check first at the head node if the value is 43. If no, it will continue to the next node by the way of the pointer and so on.
2. You can predict it will go through 4 node until it reaches the node with the value 43. If we were to search for a value that is not on the linked list it will traverse through the whole list and eventually return null.

Lets try to insert a value of 14 at index 3 in the linked list

breakdown:

1. Originally at index 3 was a node with the value of 6
2. To insert the new node (value 14) the algorithm first traverse from the head to index 3 then add the node .
3. By adding the new node we change the pointers of index 2 (value 77) to point to the new node (value 14). While the inserted node (value 14) pointer is now pointing at index node 4 (value 6)

Time to delete a node in the linked list. Lets remove the node in index 2 (value 77)

breakdown:

1. It is a fairly simple process
2. We traverse to the node in index 2 (value 77), and remove it from the list.
3. By removing the new node we change the pointers of index 1 (value 2) to point to now the new node from index 3 (value 14)

In summary Linked List is very similar to arrays when it comes to searching, inserting, or removing something in a list. But the difference comes from the Big O notation and how long it takes for each data structure to execute.

EXTRA ....EXTRA

Lets talk about a "doubly linked list". Since all of the previous example above are consider singly linked list. Here are some basic information on doubly linked list.

reference from: Geeksforgeeks

A Doubly Linked List contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

some advantages for a Doubly Linked List(DDL):

1. A DLL can be traversed in both forward and backward direction.
2. You can remove a node more efficiently disadvantage
3. Every node in a DDL require extra space for the previous pointer

Why do you need to know Linked List ?

Linked List are similar to Arrays in terms of a linear data structure. But unlike Arrays where their size is fixed and we must know the upper limit size of elements in advance, unlike Linked List which are more dynamic. Another advantage is the ease of insertion/deletion, in a linked list you do not have to create room and shift a node when you insert/delete like in Arrays, you only need to change the pointers to a new element when inserting/ deleting a new node.

In terms of Big O notation, the average time to access and search is Θ(n) slower than arrays. Insert, and delete data is Θ(1) faster than arrays.

hopefully this article was helpful.

Thanks for reading me !