Linked List

A data structure consisting of a group of nodes which together represent a sequence.

Python Example

In summary:

operations on a doubly linked list as a whole include:

  • append - adds a node to the left or right end of the list

  • insert - inserts a node before or after a specified node

  • pop - removes and returns a node from the beginning or end of the list

  • remove - removes a specified node from the list

  • nodeat - retrieves a specified node

  • clear - removes all nodes

  • first - references the first node

  • last - references the last node

  • size - references the number of nodes

operations on a specified node include:

  • next - references the node to the right

  • prev - references the node to the left

  • value - references the value

Specific Python doubly linked list functions include:

  • dllist(iterable) - double linked list creation with elements from the iterable class

  • list_name.append(n) - adds a node n to the end of a linked list

  • list_name.appendleft(n) - adds a node n to the start of a linked list

  • list_name.appendright(n) - adds a node n to the right (end) of a linked list

  • list_name.clear( ) - removes all the nodes from the linked list

  • list_name.insertafter(v, n) - add a node with value v after the node n in linked list

  • list_name.insertbefore(v, n) - add a node with value v before the node n in linked list

  • list_name.nodeat(i) - retrieves a node at index i from linked list

  • list_name.first - references the first node in linked list

  • list_name.last - references the last node in linked list

  • list_name.size - references the size of linked list

  • list_name.pop( ) - removes and returns the last node in the linked list

  • list_name.popleft( ) - removes and returns the first node in the linked list

  • list_name.popright( ) - removes and returns the last node in the linked list

  • list_name.remove(n) - removes a node n from the linked list

  • node_name.next - references the node to the right of a node N

  • node_name.prev - references the node to the left of a node N

  • node_name.value - references the value stored in a node N

The Python linked list library (llist) is described here.
The llist library will need to be installed on your system.
The example below demonstrates only a small selection of possible implementations and uses.

# Import Python linked list library methods.
from llist import dllist, dllistnode
 
# Create a double linked list with three nodes.
double_linked_list = dllist([1, 2, 3])
 
# Display the length of the list.
print(len(double_linked_list))
 
# Access a node by its index number. Indexing starts at 0.
print(double_linked_list.nodeat(1))
 
# Get the first node.
node = double_linked_list.first
 
# Display the value of the node.
print(node.value)