WOLFRAM

Wolfram Language & System Documentation Center

"DoublyLinkedList" (Data Structure)

"DoublyLinkedList"

represents a doubly linked list where the elements are general expressions.

Details

  • A doubly linked list is useful for efficiently adding and removing elements from the first and last positions:
  • CreateDataStructure["DoublyLinkedList"]create a new empty "DoublyLinkedList"
    CreateDataStructure["DoublyLinkedList",elems]create a new "DoublyLinkedList" containing elems
    Typed[x,"DoublyLinkedList"]give x the type "DoublyLinkedList"
  • For a data structure of type "DoublyLinkedList", the following operations can be used:
  • ds["Append",x]append x to dstime: O(1)
    ds["Copy"]return a copy of dstime: O(n)
    ds["DropAll"]drop all the elements from dstime: O(n)
    ds["DropFirst"]drop the first element of dstime: O(1)
    ds["DropLast"]drop the last element of dstime: O(1)
    ds["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no elementstime: O(1)
    		ds["Fold",fun]apply fun to the elements of ds, accumulating a resulttime: O(n)
    ds["Fold",fun,init]apply fun to the elements of ds, starting with init, accumulating a resulttime: O(n)
    ds["JoinBack",elems]join elems to the back of dstime: O(nelems)
    ds["JoinFront",elems]join elems to the front of dstime: O(nelems)
    ds["Length"]number of elements stored in dstime: O(1)
    ds["Part",i]give the i^(th) part of dstime: O(n)
    ds["Prepend",x]prepend x to dstime: O(1)
    ds["SetPart",i,elem]update the i^(th) part of dstime: O(n)
    ds["SwapPart",i,j]swap the i^(th) and j^(th) parts of dstime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, if dsi equals dsj
    ds["Part",i]=valset i^(th) element of ds to val
    FullForm[ds]full form of ds
    Information[ds]information about ds
    InputForm[ds]input form of ds
    Normal[ds]convert ds to a normal expression

Examples

open all close all

Basic Examples  (2)

A new "DoublyLinkedList" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["DoublyLinkedList"]

Elements can be appended:

Wolfram Language code: ds["Append", f[1]]

Elements can be prepended:

Wolfram Language code: ds["Prepend", f[2]]

Return the length:

Wolfram Language code: ds["Length"]

Extract the first element:

Wolfram Language code: ds["Part", 1]

Change an element:

Wolfram Language code: ds["Part", 1] = f[3]

The element has updated:

Wolfram Language code: ds["Part", 1]

Return an expression version of ds:

Wolfram Language code: Normal[ds]

Drop the last element:

Wolfram Language code: ds["DropLast"]; Normal[ds]

It is fast to append:

Wolfram Language code: ds = CreateDataStructure["DoublyLinkedList"]; Do[ds["Append", i], {i, 1000}]

A visualization of the data structure can be generated:

Wolfram Language code: ds["Visualization"]

Sum all the elements:

Wolfram Language code: ds["Fold", Plus, 0]

Scope  (1)

Information  (1)

A new "DoublyLinkedList" can be created with CreateDataStructure:

Wolfram Language code: ds = CreateDataStructure["DoublyLinkedList"]

Information about the data structure ds:

Wolfram Language code: Information[ds]