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.svg

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.

Continue reading “Doubly linked list”

Advertisements

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:

linkedlist

 

 

Continue reading “Linked List”