A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Rather, it is a dynamic data structure comprised of nodes pointing to other nodes which together represent a sequence. Each node contains a single item and a link to the node containing the next item. The last node in the linked list has a null value.
Singly linked lists only hold a reference to the next node. Doubly linked lists hold a reference to the next and previous nodes and can therefore be traversed in both directions.
|Singly linked||Uses less memory, simpler implementation||Cannot easily access previous elements|
|Doubly linked||Can be traversed backwards||Takes 2x memory|
|Singly linked||Doubly Linked|
|Insert at head|
|Insert at tail|
|Remove at head|
|Remove at tail|
|Remove in middle|