circular linked list Algorithm
On the other hand, since simple associated lists by themselves do not let random access to the data or any form of efficient indexing, many basic operations — such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted — may necessitate iterate through most or all of the list components. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without use a associated list as the basis.
The problem of machine translation for natural language processing led Victor Yngve at Massachusetts Institute of technology (MIT) to use associated lists as data structures in his COMIT programming language for computer research in the field of linguistics. Several operating systems developed by Technical system adviser (originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly associated lists as file structures. The now-classic diagram consisting of blocks representing list nodes with arrows indicating to successive list nodes looks in" program the logic theory machine" by Newell and Shaw in Proc.
from typing import Any
class Node:
"""
Class to represent a single node.
Each node has following attributes
* data
* next_ptr
"""
def __init__(self, data: Any):
self.data = data
self.next_ptr = None
class CircularLinkedList:
"""
Class to represent the CircularLinkedList.
CircularLinkedList has following attributes.
* head
* length
"""
def __init__(self):
self.head = None
self.length = 0
def __len__(self) -> int:
"""
Dunder method to return length of the CircularLinkedList
>>> cll = CircularLinkedList()
>>> len(cll)
0
>>> cll.append(1)
>>> len(cll)
1
>>> cll.prepend(0)
>>> len(cll)
2
>>> cll.delete_front()
>>> len(cll)
1
>>> cll.delete_rear()
>>> len(cll)
0
"""
return self.length
def __str__(self) -> str:
"""
Dunder method to represent the string representation of the CircularLinkedList
>>> cll = CircularLinkedList()
>>> print(cll)
Empty linked list
>>> cll.append(1)
>>> cll.append(2)
>>> print(cll)
<Node data=1> => <Node data=2>
"""
current_node = self.head
if not current_node:
return "Empty linked list"
results = [current_node.data]
current_node = current_node.next_ptr
while current_node != self.head:
results.append(current_node.data)
current_node = current_node.next_ptr
return " => ".join(f"<Node data={result}>" for result in results)
def append(self, data: Any) -> None:
"""
Adds a node with given data to the end of the CircularLinkedList
>>> cll = CircularLinkedList()
>>> cll.append(1)
>>> print(f"{len(cll)}: {cll}")
1: <Node data=1>
>>> cll.append(2)
>>> print(f"{len(cll)}: {cll}")
2: <Node data=1> => <Node data=2>
"""
current_node = self.head
new_node = Node(data)
new_node.next_ptr = new_node
if current_node:
while current_node.next_ptr != self.head:
current_node = current_node.next_ptr
current_node.next_ptr = new_node
new_node.next_ptr = self.head
else:
self.head = new_node
self.length += 1
def prepend(self, data: Any) -> None:
"""
Adds a ndoe with given data to the front of the CircularLinkedList
>>> cll = CircularLinkedList()
>>> cll.prepend(1)
>>> cll.prepend(2)
>>> print(f"{len(cll)}: {cll}")
2: <Node data=2> => <Node data=1>
"""
current_node = self.head
new_node = Node(data)
new_node.next_ptr = new_node
if current_node:
while current_node.next_ptr != self.head:
current_node = current_node.next_ptr
current_node.next_ptr = new_node
new_node.next_ptr = self.head
self.head = new_node
self.length += 1
def delete_front(self) -> None:
"""
Removes the 1st node from the CircularLinkedList
>>> cll = CircularLinkedList()
>>> cll.delete_front()
Traceback (most recent call last):
...
IndexError: Deleting from an empty list
>>> cll.append(1)
>>> cll.append(2)
>>> print(f"{len(cll)}: {cll}")
2: <Node data=1> => <Node data=2>
>>> cll.delete_front()
>>> print(f"{len(cll)}: {cll}")
1: <Node data=2>
>>> cll.delete_front()
>>> print(f"{len(cll)}: {cll}")
0: Empty linked list
"""
if not self.head:
raise IndexError("Deleting from an empty list")
current_node = self.head
if current_node.next_ptr == current_node:
self.head = None
else:
while current_node.next_ptr != self.head:
current_node = current_node.next_ptr
current_node.next_ptr = self.head.next_ptr
self.head = self.head.next_ptr
self.length -= 1
if not self.head:
assert self.length == 0
def delete_rear(self) -> None:
"""
Removes the last node from the CircularLinkedList
>>> cll = CircularLinkedList()
>>> cll.delete_rear()
Traceback (most recent call last):
...
IndexError: Deleting from an empty list
>>> cll.append(1)
>>> cll.append(2)
>>> print(f"{len(cll)}: {cll}")
2: <Node data=1> => <Node data=2>
>>> cll.delete_rear()
>>> print(f"{len(cll)}: {cll}")
1: <Node data=1>
>>> cll.delete_rear()
>>> print(f"{len(cll)}: {cll}")
0: Empty linked list
"""
if not self.head:
raise IndexError("Deleting from an empty list")
temp_node, current_node = self.head, self.head
if current_node.next_ptr == current_node:
self.head = None
else:
while current_node.next_ptr != self.head:
temp_node = current_node
current_node = current_node.next_ptr
temp_node.next_ptr = current_node.next_ptr
self.length -= 1
if not self.head:
assert self.length == 0
if __name__ == "__main__":
import doctest
doctest.testmod()
