What would you explain linked list to a person?
Consider a linked list to be a train where Engine is the head and you have flexibility to join locomotives or remove them . Each locomotives of the train is analogous to data node in a linked list, locomotives are connected in manner where person can go from locomotives to locomotives as you can traverse a linked list.
Insertion, deletion: Let's say train company find a locomotive to be faulty. They remove(delete) the faulty locomotive and insert a working locomotive
This would be a doubly linked list, for singly linked list you can put a restriction that person can traverse from head to last locomotives only.
Consider a linked list to be a train where Engine is the head and you have flexibility to join locomotives or remove them . Each locomotives of the train is analogous to data node in a linked list, locomotives are connected in manner where person can go from locomotives to locomotives as you can traverse a linked list.
Insertion, deletion: Let's say train company find a locomotive to be faulty. They remove(delete) the faulty locomotive and insert a working locomotive
This would be a doubly linked list, for singly linked list you can put a restriction that person can traverse from head to last locomotives only.
- In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links.
- Unlike arrays , linked list can grow or shrink in size ( size of arrays is fixed e.g. a[10]). There is ease in doing insertion and deletion in linked list than arrays. In arrays , we have to shift elements during any insertion or deletion (if sorting is maintained).
- Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
- That vectors/arrays are almost always faster because hardware memory access is optimized (caching, prefetch) for accessing contiguous addresses.
- It takes 4- 6 times the memory and 600-1000 times the CPU of a vector.
Uses of Linked List :-
- Linked lists can be used to implement stacks, queues, graphs, etc.
- Linked lists let you insert elements at the beginning and end of the list in O(1) time. This makes for efficient implementations of stacks, queues.
- Linked lists also remove the overhead of bothering about the size of the data structure. The size need not to be known in advance.
- They can also be used for the adjacency list representation of graphs.
- Hash tables with chaining is also possible.
More topics in linked list :-
Searching in Linked list
Insertion in Linked list
Deletion in linked list
Reversing Linked list
Header linked list
Circular Linked list
Doubly Linked list
No comments:
Post a Comment