In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. 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. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
Read more about Doubly Linked List: Nomenclature and Implementation
Famous quotes containing the words doubly, linked and/or list:
“For the most part, we are not where we are, but in a false position. Through an infirmity of our natures, we suppose a case, and put ourselves into it, and hence are in two cases at the same time, and it is doubly difficult to get out.”
—Henry David Thoreau (1817–1862)
“O Nature, and O soul of man! how far beyond all utterance are your linked analogies! not the smallest atom stirs or lives in matter, but has its cunning duplicate in mind.”
—Herman Melville (1819–1891)
“I am opposed to writing about the private lives of living authors and psychoanalyzing them while they are alive. Criticism is getting all mixed up with a combination of the Junior F.B.I.- men, discards from Freud and Jung and a sort of Columnist peep- hole and missing laundry list school.... Every young English professor sees gold in them dirty sheets now. Imagine what they can do with the soiled sheets of four legal beds by the same writer and you can see why their tongues are slavering.”
—Ernest Hemingway (1899–1961)