A linked list is a low-level data structure. It stores an ordered list of items in individual "node" objects that have pointers to other nodes.
In a singly linked list, the nodes each have one pointer to the next node.
So we could build a singly linked list like this:
In a linked list, the first node is called the head and the last node is called the tail.
Often, our only connection to the list itself is a variable pointing to the head. From there we can walk down the list to all the other nodes.
Like linked lists, arrays also store ordered lists of items, so you usually have a choice of which one to use.
Advantages of linked lists:
- Linked lists have constant-time insertions and deletions in any position (you just change some pointers). Arrays require time to do the same thing, because you'd have to "shift" all the subsequent items over 1 index.
Disadvantages of linked lists:
- To access or edit an item in a linked list, you have to take time to walk from the head of the list to the ith item (unless of course you already have a pointer directly to that item). Arrays have constant-time lookups and edits to the ith item.
Another type of linked list is a doubly linked list, which has pointers to the next and the previous nodes.
So we could build a doubly linked list like this:
Doubly linked lists allow us to traverse our list backwards. In a singly linked list, if you just had a pointer to a node in the middle of a list, there would be no way to know what its previous node was. Not a problem in a doubly linked list.