Linked List Simplified: Part 1

If you've just started your programming journey or it's been a while one thing you've came across many times and will surely come in future as is Data Structures and Algorithms.

They are one of the most important topics in Computer Science, as such there's a saying what differentiates a good programmer and a bad programmer is his/her knowledge of data structures and algorithms and how they apply it. It's like getting most out of your computer program with minimum resources and time available. So in order to become better at programming one should understand data structures and algorithms.

Types of Data Structures

So there are two types of data structures:

1. Linear Data Structures
2. Non-Linear Data Structures

• If you're just starting out with the data structures you might be wondering that what is a linear data structure anyway?

A linear data structure is any data structure which has/follows a sequence (i.e. data is stored one after the another) and they must be traversed linearly (sequentially)

Example of some linear data structures

In the above picture you can see the representation of array, stack and linked list all of them has one thing in common and that is they follows a sequences each block is placed after another block in a linear or sequential manner. Hence they are called linear data structure.

• Ok now we get an idea of what is a linear data structure so let's move forward with the linked list.

What is a Linked List anyway?

A Linked List is a linear data structure in which the elements are not stored in continuous memory locations.

• Think of the linked list as a chain of containers linked together
• Where the container is called as Nodes

• A Node in linked list contains data and link to its neighbour node
• The link is called pointer which either points to the next node in the linked list or Null if it's the last node in the linked list

If you're familiar with array you might be wondering that why should I use linked list if can use an array instead?

• Sure, you can definitely use an array but remember earlier in the post we talk about being a better programmer while choosing suitable data structure. So let's say you don't know the amount of data you're receiving then in such cases will it be a better idea to use array which has static memory allocation?

Memory allocation

Static memory allocation: Once the memory is allocated, the memory size cannot be changed. for e.g. array with a size of 10.

So the answer is No. We need something which should grow with our data. That's where linked list comes to rescue us.

• Unlike arrays linked list has dynamic memory allocation which means we don't have to predefined the size of the linked list which we do while using arrays. Linked list can grow and shrink dynamically with the amount of data we want to store in it.

• If have came across dynamic arrays you might say that, "Yeah but I can use dynamic arrays then why should I use Linked List"

• I have an answer to your this question as well. Let's say you want to add an item at the beginning of the array, in this case you have to first shift all the elements which are currently stored in the array by one position and then you can add the new element at the beginning. Similar to add an element in the middle of an array you have to do the same. So both the processes has a Time Complexity of O(n). Whereas in linked list the same can be achieved in O(1) time complexity.

Time complexities

Time complexities comparison of various operations in Array and Linked List

Note: In order to achieve O(1) for adding a node at the end of a linked list we have to maintain a tail pointer at the current end of the linked list just like we maintain a head pointer at the beginning of the linked list.

Types of Linked Lists

There are three types of Linked List:

1. Singly linked list : Contains only one pointer called next
2. Doubly linked list : Contains 2 pointers called previous and next
3. Circular linked list : Contains one pointer but the next pointer of the last node is connect to the first node in the linked list.

So in this post we have discuss about what is a linked list, what type of data structure category they belongs to, how they are different than arrays, when should we use them and the types of linked lists.

In the next post let's see how to create a linked list from scratch, what are their Pros and Cons and some additional information regarding the linked lists.

Vote of Thanks

Thank you so much for reading this post and I hope you find this post useful. Feel Free to give any suggestions and if you like my work you can follow me on Twitter