WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

"LinkedList" (Data Structure)

"LinkedList"

represents a linked list where the elements are general expressions.

Details

  • A linked list is useful for efficiently prepending and appending elements:
  • CreateDataStructure["LinkedList"]create a new empty "LinkedList"
    CreateDataStructure["LinkedList",elems]create a new empty "LinkedList" containing elems
    Typed[x,"LinkedList"]give x the type "LinkedList"
  • For a data structure of type "LinkedList", 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["Elements"]return a list of the elements of dstime: O(n)
    ds["EmptyQ"]True, if ds has no elementstime: O(1)
    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 allclose all

Basic Examples  (2)Summary of the most common use cases

A new "LinkedList" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-ck3oom
Out[1]=1

Elements can be appended:

In[2]:=2
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-84r1md
Out[2]=2

Elements can be prepended:

In[3]:=3
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-9lv49k
Out[3]=3

Return the length:

In[4]:=4
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-tnm4iz
Out[4]=4

Extract the first element:

In[5]:=5
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-kfcutb
Out[5]=5

Change an element:

In[6]:=6
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-2ymbbr
Out[6]=6

The element has updated:

In[7]:=7
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-3dkxgf
Out[7]=7

Return an expression version of ds:

In[8]:=8
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-dbekgb
Out[8]=8

It is fast to append and prepend:

In[1]:=1
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-mfljzp

A visualization of the data structure can be generated:

In[2]:=2
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-uvwa1b
Out[2]=2

Sum all the elements:

In[3]:=3
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-volwmf
Out[3]=3

Scope  (1)Survey of the scope of standard use cases

Information  (1)

A new "LinkedList" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-vilja1
Out[1]=1

Information about the data structure ds:

In[2]:=2
✖
https://wolfram.com/xid/0b6j9o3c859pu0ijhzn04q-5du3om
Out[2]=2