Often while preparing for interviews students forget to brush up some basic facts and topics which results in under-cooked performance. Although having said that I would like to shed some light on the concept of linked list.
- Linked list
Linked list basically is a type of data structure use to store elements of a particular type. It uses node system where every node has a link to the next node and stores data. Now you might be thinking that What the heck is node system ? Node is basically a record holding data and reference. In simple words linked list is the formation of sequentially connected records holding data and reference.
- Why Linked list ?
Now this is quite the trap to escape. You could argue that we can use array but the fact where linked list proves more efficient is you can play with pointers which is not the case with arrays. Insertion and deletion is much faster and dynamic memory allocation makes it perfect fit for complex addressing. No memory fragmentation issue and no compulsion of defining size.
The basic advantage of linked list when comparing with array is that, you can dynamically insert node, which is not the case with arrays as it has a fixed size already defined.
- What is singly linked list ?
Singly linked list simply contains the data in the node and reference to the next one. It does not contain any link to the previous node. One node will be there which will not contain any reference for next node and that node is the last node. They are most simple and easy to implement but their practical usage is in limit.
- What is doubly linked list ?
Doubly linked list differs from the singly in the way it holds the reference to the previous node along with storing its own data and address of next node. The last node will contain only the reference to the previous node and no address of next node as obvious it is the last node.
- What is circular linked list ?
It can be of two types :
- circular linked list
- circular doubly linked list
As it is circular, you will get an idea that its last node will be connected to the first node. Hence the last node will contain reference to first node.
- What are the applications of linked list ?
Binary tree, hash table, queues, stacks are few among many.
Apart from these basic questions you people can also go through some code snippets regarding linked list:
- How to add element in the starting of singly & doubly linked list?
- How to delete a particular element in the middle of singly & doubly linked list? (Note: for doubly linked list both front and rear node will come into play)
- Similarly the delete operation is equally important.
- Also how to display the linked list from first to last and vice versa.
- How to add new node in the linked list?