Doubly linked list

The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

The references stored in the link fields are usually implemented as pointers, but (as in any linked data structure), they may also be address offsets or indices into an array where the nodes live.

Consider the following basic algorithms written in Ada: Traversal of a doubly linked list can be in either direction.

Assuming that someNode is some node in a non-empty list, this code traverses through that list starting with someNode (any node will do): Forwards Backwards Notice the postponing of the test to the end of the loop.

A doubly linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.
A doubly linked list whose nodes contain three fields: the link to the previous node, an integer value, and the link to the next node.