Posts tagged "list"

Linked List

Here’s a very simple implementation of the linked list data structure.

A pointer to the head element is enough to define a linked list. Each element consists of one pointer to the subsequent element in the list and one pointer to the element’s data:

linkedlis

Doubly linked list

A doubly linked list is like our previously implemented Linked List, but instead of only having pointers to the next element, it also has pointers to the _previous _element:

610px-Doubly-linked-list.sv

This property makes the doubly linked list very useful as a base for other data structures such as the stack: having a previous pointer means we can quickly (O(1)) remove objects from the list’s tail, which would be impossible with a linked list.

We won’t discuss implementation since it so similar to a linked list. If anything implementation is even simpler than a linked list because of the previous pointer access.