Linked Lists

class pydatastructs.SinglyLinkedList

Represents Singly Linked List

Examples

>>> from pydatastructs import SinglyLinkedList
>>> sll = SinglyLinkedList()
>>> sll.append(6)
>>> sll[0].key
6
>>> sll.head.key
6
>>> sll.append(5)
>>> sll.appendleft(2)
>>> str(sll)
"['(2, None)', '(6, None)', '(5, None)']"
>>> sll[0].key = 7.2
>>> sll.extract(1).key
6
>>> str(sll)
"['(7.2, None)', '(5, None)']"

References

1

https://en.wikipedia.org/wiki/Singly_linked_list

insert_after(prev_node, key, data=None)

Inserts a new node after the prev_node.

Parameters

  • prev_node (LinkedListNode) – The node after which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_at(index, key, data=None)

Inserts a new node at the input index.

Parameters

  • index (int) – An integer satisfying python indexing properties.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

extract(index)

Extracts the node at the index of the list.

Parameters

index (int) – An integer satisfying python indexing properties.

Returns

current_node – The node at index i.

Return type

LinkedListNode

head
tail
size
__module__ = 'pydatastructs.linear_data_structures.linked_lists'
class pydatastructs.DoublyLinkedList

Represents Doubly Linked List

Examples

>>> from pydatastructs import DoublyLinkedList
>>> dll = DoublyLinkedList()
>>> dll.append(6)
>>> dll[0].key
6
>>> dll.head.key
6
>>> dll.append(5)
>>> dll.appendleft(2)
>>> str(dll)
"['(2, None)', '(6, None)', '(5, None)']"
>>> dll[0].key = 7.2
>>> dll.extract(1).key
6
>>> str(dll)
"['(7.2, None)', '(5, None)']"

References

1

https://en.wikipedia.org/wiki/Doubly_linked_list

insert_after(prev_node, key, data=None)

Inserts a new node after the prev_node.

Parameters

  • prev_node (LinkedListNode) – The node after which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_before(next_node, key, data=None)

Inserts a new node before the next_node.

Parameters

  • next_node (LinkedListNode) – The node before which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_at(index, key, data=None)

Inserts a new node at the input index.

Parameters

  • index (int) – An integer satisfying python indexing properties.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

extract(index)

Extracts the node at the index of the list.

Parameters

index (int) – An integer satisfying python indexing properties.

Returns

current_node – The node at index i.

Return type

LinkedListNode

head
tail
size
__module__ = 'pydatastructs.linear_data_structures.linked_lists'
class pydatastructs.SinglyCircularLinkedList

Represents Singly Circular Linked List.

Examples

>>> from pydatastructs import SinglyCircularLinkedList
>>> scll = SinglyCircularLinkedList()
>>> scll.append(6)
>>> scll[0].key
6
>>> scll.head.key
6
>>> scll.append(5)
>>> scll.appendleft(2)
>>> str(scll)
"['(2, None)', '(6, None)', '(5, None)']"
>>> scll[0].key = 7.2
>>> scll.extract(1).key
6
>>> str(scll)
"['(7.2, None)', '(5, None)']"

References

1

https://en.wikipedia.org/wiki/Linked_list#Circular_linked_list

insert_after(prev_node, key, data=None)

Inserts a new node after the prev_node.

Parameters

  • prev_node (LinkedListNode) – The node after which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_at(index, key, data=None)

Inserts a new node at the input index.

Parameters

  • index (int) – An integer satisfying python indexing properties.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

extract(index)

Extracts the node at the index of the list.

Parameters

index (int) – An integer satisfying python indexing properties.

Returns

current_node – The node at index i.

Return type

LinkedListNode

head
tail
size
__module__ = 'pydatastructs.linear_data_structures.linked_lists'
class pydatastructs.DoublyCircularLinkedList

Represents Doubly Circular Linked List

Examples

>>> from pydatastructs import DoublyCircularLinkedList
>>> dcll = DoublyCircularLinkedList()
>>> dcll.append(6)
>>> dcll[0].key
6
>>> dcll.head.key
6
>>> dcll.append(5)
>>> dcll.appendleft(2)
>>> str(dcll)
"['(2, None)', '(6, None)', '(5, None)']"
>>> dcll[0].key = 7.2
>>> dcll.extract(1).key
6
>>> str(dcll)
"['(7.2, None)', '(5, None)']"

References

1

https://en.wikipedia.org/wiki/Doubly_linked_list#Circular_doubly_linked_lists

insert_after(prev_node, key, data=None)

Inserts a new node after the prev_node.

Parameters

  • prev_node (LinkedListNode) – The node after which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_before(next_node, key, data=None)

Inserts a new node before the next_node.

Parameters

  • next_node (LinkedListNode) – The node before which the new node is to be inserted.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

insert_at(index, key, data=None)

Inserts a new node at the input index.

Parameters

  • index (int) – An integer satisfying python indexing properties.

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

extract(index)

Extracts the node at the index of the list.

Parameters

index (int) – An integer satisfying python indexing properties.

Returns

current_node – The node at index i.

Return type

LinkedListNode

head
tail
size
__module__ = 'pydatastructs.linear_data_structures.linked_lists'
class pydatastructs.SkipList

Represents Skip List

Examples

>>> from pydatastructs import SkipList
>>> sl = SkipList()
>>> sl.insert(6)
>>> sl.insert(1)
>>> sl.insert(3)
>>> node = sl.extract(1)
>>> str(node)
'(1, None)'
>>> sl.insert(4)
>>> sl.insert(2)
>>> sl.search(4)
True
>>> sl.search(10)
False
property levels

Returns the number of levels in the current skip list.

search(key) → bool
insert(key, data=None)

Inserts a new node to the skip list.

Parameters

  • key – Any valid identifier to uniquely identify the node in the linked list.

  • data – Any valid data to be stored in the node.

property size
extract(key)

Extracts the node with the given key in the skip list.

Parameters

key – The key of the node under consideration.

Returns

return_node – The node with given key.

Return type

SkipNode

__str__()

Return str(self).

head
tail
seed
__module__ = 'pydatastructs.linear_data_structures.linked_lists'