Doubly Linked List

The pyTooling.LinkedList package …

Example Doubly Linked List:

        %%{init: { "flowchart": { "nodeSpacing": 15, "rankSpacing": 30, "curve": "linear", "useMaxWidth": false } } }%%
graph LR
  LL(LinkedList); A(Node 0); B(Node 1); C(Node 2); D(Node 3); E(Node 4)

  LL:::mark1 --> A
  LL --> E
  A <--> B <--> C <--> D <--> E

  classDef node fill:#eee,stroke:#777,font-size:smaller;
  classDef cur fill:#9e9,stroke:#6e6;
  classDef mark1 fill:#69f,stroke:#37f,color:#eee;

A linked list graph.

Doubly Linked List Properties:

The LinkedList counts the number of elements.
The LinkedList has a reference to the first and last element in the doubly linked list.
Each Node has a linked to its previous Node and its next Node (doubly linked).
Each Node has a link to its LinkedList.
Each Node has a value.
Operations can be performed in the LinkedList or on any Node.
The LinkedList can be iterated in ascending and descending order.
The list can be iterated starting from any Node.

Features

Insert operations can be performed in the LinkedList or on any Node.
Remove operations can be performed in the LinkedList or on any Node.
The LinkedList can be iterated in ascending and descending order.
The LinkedList can be cleared.
TBD

Missing Features

TBD

Planned Features

TBD

Out of Scope

TBD

By Property

Linked List Properties

is empty
count
first
last

Node Properties

PreviousNode
NextNode
Value
List

By Operation

Danger

Accessing internal fields of a doubly linked list or node is strongly not recommended for users, as it might lead to a corrupted data structure. If a power-user wants to access these fields, feel free to use them for achieving a higher performance, but you got warned 😉.

Instantiation

The LinkedList can be instantiated as an empty linked list without any aditional parameters. It will report as empty via property LinkedList.IsEmpty and report zero elements via property LinkedList.Count.

Alternatively, it can be constructed from an iterable like a tuple, list or any Python iterator. The order of the iterable is preserved.

The time complexity is O(n).

Empty LinkedList

from pyTooling.LinkedList import LinkedList


ll = LinkedList()

ll.IsEmpty
# => True
ll.Count
# => 0

LinkedList from tuple

from pyTooling.LinkedList import LinkedList

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

ll.IsEmpty
# => False
ll.Count
# => 5

Clear

The LinkedList can be cleared by calling the LinkedList.Clear method. Afterwards, the linked list reports as empty and a count of zero.

The time complexity is O(1).

Clearing a LinkedList

from pyTooling.LinkedList import LinkedList

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

ll.Clear()

ll.IsEmpty
# => False
ll.Count
# => 5

Insert

A new Node can be inserted into the linked list at any position.

Very fast insertions into the linked list can be achieved before the the first element using LinkedList.InsertBeforeFirst or after the last element using LinkedList.InsertAfterLast

Additionally, if there is a reference to a specific node of the linked list, insertions before and after that node are also very efficient. The methods are LinkedList.InsertNodeBefore and LinkedList.InsertNodeAfter.

The time complexity is O(1).

Before first node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

newNode = Node(0)
ll.InsertBeforeFirst(newNode)

After last node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

newNode = Node(6)
ll.InsertAfterLast(newNode)

Before current node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

node = ll[2]

newNode = Node(2.5)
node.InsertNodeBefore(newNode)

After current node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

node = ll[2]

newNode = Node(3.5)
node.InsertNodeAfter(newNode)

Random Access Insert

Inserting a new node at a random postion is less efficient then direct inserts at the first or last element of the linked list or before and after a specific node. The additional effort comes from walking the linked list to find the n-th element. Then an efficient insert is performed.

The linked list is walked from the shorter end.

The time complexity is O(n/2).

Before first n-th node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

newNode = Node(2.5)
ll.InsertNodeBefore(2, newNode)

Before after n-th node

from pyTooling.LinkedList import LinkedList, Node

initTuple = (1, 2, 3, 4, 5)
ll = LinkedList(initTuple)

newNode = Node(3.5)
ll.InsertNodeAfter(2, newNode)

Remove

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

First node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Last node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Current node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

At position

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

By predicate

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Iterate

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

Forward from first node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Backward from last node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Forward from current node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Backward from current node

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Sort

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

Ascending

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Descending

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Reverse

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

Reverse

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Search

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

By predicate

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Convert

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

To tuple

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

To list

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Item Access

A new Node can be inserted into the linked list at any position.

Very fast insertions can be achieved before the the first element using LinkedList.InsertBeforeFirst

The time complexity is O(1).

Get value

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Set value

from pyTooling.LinkedList import LinkedList

ll = LinkedList()

Delete value

from pyTooling.LinkedList import LinkedList

ll = LinkedList()