Linked list
A linked list is some sort of linear data structure, and the elements are not stored at contiguous memory location. The elements in the linked list are linked using pointers. In other words, a linked list consists of nodes where each node contains a data field and a reference to the next node in the list.
Linked list had some advantages over arrays such as dynamic size and ease of insertion/deletion.
But there are some drawbacks on using linked list as listed below:
1.) Random access is not allowed. We have to sequentially access the elements starting from the first node. So we cant do binary search efficiently with its default implementation.
2.) Each element on the list requires an extra memory space for a pointer
3.) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked list.
A linked list is represented by a pointer from the first node of the linked list. The first node is called the "head". If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least data and pointer. In C, we can represent a node using structures, but in Java or C#, linked list class contains a reference of node class type.
Linked list had some advantages over arrays such as dynamic size and ease of insertion/deletion.
But there are some drawbacks on using linked list as listed below:
1.) Random access is not allowed. We have to sequentially access the elements starting from the first node. So we cant do binary search efficiently with its default implementation.
2.) Each element on the list requires an extra memory space for a pointer
3.) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked list.
A linked list is represented by a pointer from the first node of the linked list. The first node is called the "head". If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least data and pointer. In C, we can represent a node using structures, but in Java or C#, linked list class contains a reference of node class type.
Comments
Post a Comment