I have been asked this question continuously in various technical interviews but I have never been able to give the perfect answer. I will try to jot my understanding of Linked Lists here.
So let us get back to Data Structures. Data Structures are the beautiful and most important topic in the world of Computer science. How to structure your data to save memory and time is what defines a better engineer. Broadly speaking, they are of two types:
- Linear Data Structures
- Non-Linear Data Structures
Linear Data Structures: They can be traversed only sequentially. One of the classic example if of an Array. An array is defined in contiguous memory locations and its memory is fixed. Memory Management is an important aspect of Linear Data Structures. For Adding new data to existing array one needs to copy it and then add the new data. Linked List is also a type of linear data structure.
Non-Linear Data Structures: They can be traversed in the non sequential way. Graphs, and Trees are classic examples of this type of data structure.
Let us get started with Linked Lists.
Linked Lists consists of nodes. Starting node is called as HEAD.
Each node has Two parts. One part consists of Data and other holds the address or memory reference of the next neighboring node. The end of linked list occurs when during traversal a null is encountered.
Linked lists are three types:
- Singly Linked Lists: Each node holds the address of only next node.
- Doubly Linked Lists: Each node here holds the address of preceding node as well as the node next to it.
- Circular Linked Lists: These start and end at the same node called as TAIL.
In next blog, we will dive little deeper into how linked lists manage time and space.