分类: C/C++
2012-05-08 16:27:23
In , a doubly-linked list is a that
consists of a set of , each having two special link that
contain to the previous and to the next record in the sequence.
It can be viewed as two formed from the same data items,
in two opposite orders. A doubly-linked list whose nodes contains three fields:
an integer value, the link to the next node, and the link to the previous node.
The two links allow walking along the list in either direction with equal ease.
Contents []
|
(as in any linked data structure) they may also be address offsets or indices into
an where the nodes live.
The link fields are often called forward and backwards, or next and previous.
A pointer to any node of a doubly-linked list gives access to the whole list. However,
it's usually convenient to handle the list by the pointers of the first and last nodes,
e.g. when passing it to .
Basic algorithms Open doubly-linked lists Data type declarations record Node {Iterating through a doubly linked list can be done in either direction. In fact, direction can
change many times, if desired.
Forwards
node := list.firstNodeBackwards
node := list.lastNodeThese symmetric functions add a node either after or before a given node, with the
diagram demonstrating after:
function insertAfter(List list, Node node, Node newNode)We also need a function to insert a node at the beginning of a possibly-empty list:
function insertBeginning(List list, Node newNode)A symmetric function inserts at the end:
function insertEnd(List list, Node newNode)Removing a node is easier, only requiring care with the firstNode and lastNode:
function remove(List list, Node node)One subtle consequence of this procedure is that deleting the last element of a list
sets both firstNode and lastNode to null, and so it handles removing the last node
from a one-element list correctly. Notice that we also don't need separate "removeBefore"
or "removeAfter" methods, because in a doubly-linked list we can just use "remove(node.prev)"
or "remove(node.next)" where these are valid.
Circular Doubly-linked lists Iterating over the elementsAssuming that someNode is some node in a non-empty list, this code iterates through
that list starting with someNode (any node will do):
Forwards
node := someNodeBackwards
node := someNodeNotice the postponing of the test to the end of the loop. This is important for the
case where the list contains only the single node someNode.
Inserting a nodeThis simple function inserts a node into a doubly-linked circularly-linked list after
a given element:
function insertAfter(Node node, Node newNode)To do an "insertBefore", we can simply "insertAfter(node.prev, newNode)". Inserting
an element in a possibly empty list requires a special function:
function insertEnd(List list, Node node)To insert at the beginning we simply "insertAfter(list.lastNode, node)". Finally,
removing a node must deal with the case where the list empties:
function remove(List list, Node node)This article does not any . Please help improve this article by adding citations to . Unsourced material may be and . (April 2009) |