Positional Doubly Linked List

This Python script implements a Positional Doubly Linked List, a data structure that allows for efficient insertion, deletion, and traversal of elements in both forward and backward directions. The list is designed to provide positional access to nodes, enabling operations like adding, deleting, and swapping elements at specific positions.

Features

• Doubly Linked List: Each node contains references to both the next and previous nodes, allowing for bidirectional traversal.
• Positional Access: Nodes are accessed via position objects, which act as handles to specific nodes in the list.
• Basic Operations:
  • Add/Remove Elements: Add or remove elements at the beginning, end, or any specific position in the list.
  • Swap Nodes: Swap the values or positions of two nodes in the list.
  • Sorting: Sort the list in ascending order or based on access counts.
  • Iteration: Iterate through the list using Python's __iter__ method.
  • Reversing: Reverse the order of elements in the list.
• Advanced Operations:
  • Merge Lists: Merge two lists with or without modifying the original lists.
  • Positional Manipulation: Add, delete, or swap nodes based on their positions.

Usage

Initialization

To create a new positional doubly linked list:

plist = positional_doubly_linkedlist()

Adding Elements

• Add to the beginning:

  plist.insert_first(10)

• Add to the end:

  plist.insert_last(20)

• Add at a specific position:

  pos = plist.get_first_position()  # Get the first position
  plist.add_after(pos, 15)  # Add 15 after the first position

Removing Elements

• Remove the first element:

  plist.delete_first()

• Remove the last element:

  plist.delete_last()

• Remove a specific element:

  pos = plist.get_first_position()  # Get the first position
  plist.delete_at_position(pos)  # Delete the first element

Swapping Nodes

• Swap values of two nodes:

  pos1 = plist.get_first_position()
  pos2 = plist.get_last_position()
  plist.swap_data_at_positions(pos1, pos2)

Sorting

• Sort in ascending order:

  sorted_list = plist.sort()

• Sort based on access counts:

  sorted_list = plist.access_sort(plist.head._next, plist.tail._prev)

Iteration

• Iterate through the list:

  for node in plist:
      print(node.data)

Reversing the List

• Reverse the list:

  reversed_list = plist.reverse()

Merging Lists

• Merge two lists with changes:

  y = positional_doubly_linkedlist()
  y.insert_first(30)
  plist.merge_with_changes(y)

• Merge two lists without changes:

  merged_list = plist.merge_no_changes(y)

Finding Elements

• Find the first occurrence of a value:

  pos = plist.search(10)

Example

plist = positional_doubly_linkedlist()
plist.insert_first(6)
plist.insert_first(4)
plist.insert_first(2)
plist.insert_last(555)

print(plist)  # Output: head-->2-->4-->6-->555-->tail

# Reverse the list
reversed_list = plist.reverse()
print(reversed_list)  # Output: head-->555-->6-->4-->2-->tail

# Sort the list in ascending order
sorted_list = plist.sort()
for node in sorted_list:
    print(node.data)  # Output: 2, 4, 6, 555

Notes

• The list uses sentinel nodes (head and tail) to simplify boundary conditions.
• The position class acts as a handle to nodes, allowing for safe and efficient manipulation of the list.
• The list supports 1-based indexing for positional operations.