Doubly Linked List¶

⏱ Time-Complexity¶

The following table sums up all the different public functionality in this class and also provides the worst-case time complexity along side with the optimal time complexity that I will try to reach in future releases Insha’Allah. Generally, we are going to use the following indicators in the table:

• n is the number of elements currently in the doubly linked list.
• m is the number of elements in the other doubly linked list.
• k is the value of a given index.

☕️ API¶

Here are all of the public methods that can be used with DoublyLinkedList() objects:

class extra.lists.doubly_linked_list.DoublyLinkedList(iterable=None)¶

A doubly linked list is a simple linear data structure where objects are linked using pointers to their associated location. Unlike arrays whose objects are stored at continuous locations. Each node stores two references: the first is a reference to the next element of the sequence. And the other is a reference to the previous element of the sequence.

__contains__(value)¶

Checks if the given value exists in the DoublyLinkedList() instance in time-complexity of O(n) where n is the total number of elements in the DoublyLinkedList() instance.

Parameters:	value (Object) – The value to be searched for in the DoublyLinkedList() instance.
Returns:	True if the given value exists in the DoublyLinkedList() instance, and False otherwise.
Return type:	bool

Examples

>>> dll = DoublyLinkedList([1, 3, 5])
>>> 1 in dll
True
>>> 0 in dll
False
>>> "hello" in dll
False

__delitem__(idx)¶

Deletes the value at the given index. It does that in time-complexity of O(min(k,n/2)) where k is the index value and n is the number of elements in the DoublyLinkedList() instance.

Parameters:	idx (int) – An integer pointing to the index where the node that should be removed.
Raises:	IndexError: – If the given index is either negative or out of the boundaries.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll
 ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘
>>> del dll[0]
>>> dll
 ┌───┐ ┌───┐
⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘
>>> del dll[-1]
IndexError: Negative indexing isn't supported with this functinoality!!
>>> del dll[3]
IndexError: Given index is out of the boundaries!!

__eq__(other)¶

Checks if two DoublyLinkedList() instances are equal to each other. And this happens if, and only if, the following two conditions are met:

1. The two instances are equal in length (same number of elements).

2. Every single element in the first instance is equal, in both

   value and type, to the opposing element of the other instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if both instances are equal, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 3, 2])
>>> dll_1 == dll_2
False
>>> dll_1 == dll_1
True

__ge__(other)¶

Checks if the first DoublyLinkedList() instance is greater than or equal to the other instance. And this happens if all elements in the first instance are greater than or equal to the opposing element of the second instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if the first instance is greater than or equal to the second, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 3, 5])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 >= dll_2
True

>>> dll_1 = DoublyLinkedList([1, 3, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 2])
>>> dll_1 >= dll_2
True

>>> dll_1 = DoublyLinkedList([1, 2])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 >= dll_2
False

>>> dll_1 = DoublyLinkedList([5, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 >= dll_2
False

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 2, 3])
>>> dll_1 >= dll_2
True

__getitem__(idx)¶

Retrieves the element at the given index. The given index could be a zero-based int or a slice object. This method supports negative indexing. This method does that in time-complexity of O(k) where k is the given index.

Parameters:	idx (int or slice) – The index (multiple indices) to be used to retrieve values from the DoublyLinkedList() instance.
Returns:	If the given index is an int, then it returns the value at this index. If the given index is a slice object, then it returns a DoublyLinkedList() instance containing the desired values.
Return type:	object or DoublyLinkedList()
Raises:	TypeError: – If the given index isn’t int. IndexError: – If the given index is out of the DoublyLinkedList() boundaries.

Examples

>>> dll = DoublyLinkedList([1, 2, 3, 4, 5])
>>> dll[0]
1
>>> dll[-2]
4
>>> dll[2:]
 ┌───┐ ┌───┐ ┌───┐
⟷│ 3 │⟷│ 4 │⟷│ 5 │⟷
 └───┘ └───┘ └───┘
>>> dll[0:5:2]
 ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 3 │⟷│ 5 │⟷
 └───┘ └───┘ └───┘
>>> dll[10]
IndexError: Given index is out of the boundaries!!

__gt__(other)¶

Checks if the first DoublyLinkedList() instance is greater than the other instance. And this happens if all elements in the first instance are equal with at least one element greater than the opposing element of the second instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if the first instance is greater than the second, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 3, 5])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 > dll_2
True

>>> dll_1 = DoublyLinkedList([1, 3, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 2])
>>> dll_1 > dll_2
True

>>> dll_1 = DoublyLinkedList([1, 2])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 > dll_2
False

>>> dll_1 = DoublyLinkedList([5, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 > dll_2
False

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 2, 3])
>>> dll_1 > dll_2
False

__init__(iterable=None)¶

Initializes a DoublyLinkedList() instance using an optional iterable object in time-complexity of O(n) where n is the number of elements inside the given iterable.

Parameters:	iterable (iterable object, optional) – An iterable python object that implements the __iter__ method. For example, list and tuple are both iterables.
Returns:	It returns a DoublyLinkedList() instance with the same values in the same order.
Return type:	DoublyLinkedList()
Raises:	TypeError: – It can be raised in two cases In case the given object isn’t iterable. If one of the iterable elements is an Extra object. ValueError: – If one of the iterable elements is None.

Examples

>>> dll = DoublyLinkedList([10, -5, 7, 9])
>>> dll
 ┌────┐ ┌────┐ ┌───┐ ┌───┐
⟷│ 10 │⟷│ -5 │⟷│ 7 │⟷│ 9 │⟷
 └────┘ └────┘ └───┘ └───┘

Using an iterable object with None as one of its elements will raise ValueError

>>> DoublyLinkedList([2, None])
ValueError: Can't use `None` as an element within             `extra.DoublyLinkedList()`!!

Using a non-iterable object will raise TypeError

>>> DoublyLinkedList(2)
TypeError: The given object isn't iterable!!

Using nested DoublyLinkedList objects will raise TypeError as well

>>> dll_1 = DoublyLinkedList([1])
>>> dll_2 = DoublyLinkedList([1, dll_1])
TypeError: Can't create `extra.DoublyLinkedList()` using             `extra.DoublyLinkedList()`!!

Note

Since most of the data structures found in this package are iterables, then you can use this classmethod to convert from one data structure to DoublyLinkedList just like so:

>>> ll = LinkedList([2, 5])
>>> ll
┌───┐ ┌───┐
│ 2 │⟶│ 5 │⟶
└───┘ └───┘
>>> dll = DoublyLinkedList(ll)
>>> dll
 ┌───┐ ┌───┐
⟷│ 2 │⟷│ 5 │⟷
 └───┘ └───┘

__iter__()¶

Iterates over the DoublyLinkedList() instance and returns a generator in time-complexity of O(n) where n is the number of elements in the DoublyLinkedList() instance.

Yields:	pbect – The value stored inside each node in the instance.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> for item in dll:
...     print(item)
1
2
3

__le__(other)¶

Checks if the first DoublyLinkedList() instance is less than or equal to the other instance. And this happens if all elements in the first instance are equal or less than the opposing elements of the second instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if the first instance is less than or equal to the second instance, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 3, 2])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 <= dll_2
True

>>> dll_1 = DoublyLinkedList([1, 3])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 <= dll_2
True

>>> dll_1 = DoublyLinkedList([1, 5])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 <= dll_2
False

>>> dll_1 = DoublyLinkedList([5, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 <= dll_2
False

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 2, 3])
>>> dll_1 <= dll_2
True

__len__()¶

Gets the length of the DoublyLinkedList() in constant time.

Returns:	The length of the DoublyLinkedList() instance. By Length, I mean the number of nodes of in the instance.
Return type:	int

Examples

>>> dll = DoublyLinkedList()
>>> len(dll)
0
>>> dll = DoublyLinkedList((2, 5, 0))
>>> len(dll)
3

__lt__(other)¶

Checks if the first DoublyLinkedList() instance is less than the other instance. And this happens if all elements in the first instance are equal with at least one element less than the opposing element of the second instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if the first instance is less than the second, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 3, 2])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 < dll_2
True

>>> dll_1 = DoublyLinkedList([1, 3])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 < dll_2
True

>>> dll_1 = DoublyLinkedList([1, 5])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 < dll_2
False

>>> dll_1 = DoublyLinkedList([5, 2, 1])
>>> dll_2 = DoublyLinkedList([1, 3, 3])
>>> dll_1 < dll_2
False

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 2, 3])
>>> dll_1 < dll_2
False

__ne__(other)¶

Checks if two DoublyLinkedList() instances are NOT equal to each other. And this happens if, and only if, either one of the following two conditions is satisfied:

1. The two instances are NOT equal in length (number of elements).

2. Just one element in the first instance is NOT equal, in either value or type, to the opposing element of the other instance.

Parameters:	other (DoublyLinkedList()) – The other instance that we want to compare with the current one
Returns:	True if both instances are NOT equal, and False otherwise.
Return type:	bool
Raises:	TypeError: – This happens in two cases 1. If the other instance isn’t a DoublyLinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> dll_1 = DoublyLinkedList([1, 2, 3])
>>> dll_2 = DoublyLinkedList([1, 3, 2])
>>> dll_1 != dll_2
True
>>> dll_1 != dll_1
False

__repr__()¶

Represents the DoublyLinkedList() instance as a string.

Returns:	The string-representation of the DoublyLinkedList() instance.
Return type:	str

Example

>>> dll = DoublyLinkedList([20, 77, 10, 6, 2])
>>> dll
 ┌────┐ ┌────┐ ┌────┐ ┌───┐ ┌───┐
⟷│ 20 │⟷│ 77 │⟷│ 10 │⟷│ 6 │⟷│ 2 │⟷
 └────┘ └────┘ └────┘ └───┘ └───┘

__setitem__(idx, item)¶

Replaces the value at the given index with the given item. It does that in time-complexity of O(min(k,n/2)) where k is the index value and n is the number of elements in the DoublyLinkedList() instance.

Parameters:	idx (int) – An integer pointing to the index at which the given value should be inserted. item (object) – An object to be inserted.
Raises:	IndexError: – If the given index is either negative or out of the boundaries. ValueError: – If the given object is None. TypeError: – This get raised in one of the following cases: If the given index type is not int. If the given object is an instance of Extra.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll
 ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘
>>> dll[0] = 10
>>> dll[2] = 30
>>> dll
 ┌────┐ ┌───┐ ┌────┐
⟷│ 10 │⟷│ 2 │⟷│ 30 │⟷
 └────┘ └───┘ └────┘
>>> dll[-1] = 0
IndexError: Negative indexing isn't supported with this functinoality!!
>>> dll[3] = 40
IndexError: Given index is out of the boundaries!!

add_end(item)¶

Adds the given value at the tail of the DoublyLinkedList() instance in constant time.

Parameters:	item (object) – The value to be inserted at the DoublyLinkedList() tail.
Raises:	TypeError: – If the given item is an instance of Extra. ValueError: – If the given item is None.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll.add_end(10)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌────┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 10 │⟷
 └───┘ └───┘ └───┘ └────┘

add_front(item)¶

Adds the given value at the head of the DoublyLinkedList() instance in constant time.

Parameters:	item (object) – The value to be inserted at the DoublyLinkedList() head.
Raises:	TypeError: – If the given item is an instance of Extra. ValueError: – If the given item is None.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll.add_front(10)
>>> dll
 ┌────┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 10 │⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └────┘ └───┘ └───┘ └───┘

clear()¶

Removes all nodes within the DoublyLinkedList() in constant time.

Example

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll
 ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘
>>> dll.clear()
>>> dll.is_empty()
True
>>> dll
┌─
│
└─

copy()¶

Copies the DoublyLinkedList() instance in a shallow-manner.

Returns:	The shallow copy of the original instance.
Return type:	DoublyLinkedList()

Example

>>> dll = DoublyLinkedList()
>>> dll.add_end(10)
>>> dll.add_end(20)
>>> dll
 ┌────┐ ┌────┐
⟷│ 10 │⟷│ 20 │⟷
 └────┘ └────┘
>>> dll.copy()
 ┌────┐ ┌────┐
⟷│ 10 │⟷│ 20 │⟷
 └────┘ └────┘

count(value)¶

Counts the number of occurrence the given value is in the DoublyLinkedList() instance.

Parameters:	value (object) – The object to count its occurrences
Returns:	The number of times the given value is found in the DoublyLinkedList() instance. And 0 if it wasn’t found.
Return type:	int

Example

>>> dll = DoublyLinkedList([0, 1, 1, 2, 3, 5])
>>> dll.count(3)
1
>>> dll.count(1)
2
>>> dll.count("he")
0

extend(other)¶

Extends the current DoublyLinkedList() instance by appending the elements of the other DoublyLinkedList() instance in constant time.

Parameters:	other (DoublyLinkedList()) – The DoublyLinkedList() instance whose elements will be appended.
Raises:	TypeError: – If the given object isn’t a DoublyLinkedList() instance.

Example

>>> dll_1 = DoublyLinkedList([1, 2])
>>> dll_2 = DoublyLinkedList([3, 4, 5])
>>> dll_1.extend(dll_2)
>>> dll_1
 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷│ 5 │⟷
 └───┘ └───┘ └───┘ └───┘ └───┘
>>> dll_1.extend([6, 7])
TypeError: Type Mismatch! Can't extend `extra.DoublyLinkedList()` with
`<class 'list'>`!!

insert(idx, item)¶

Insertd a value at a position defined by the given index to the DoublyLinkedList() instance.

Parameters:	idx (int) – An integer pointing to the index at which the given value should be inserted. item (object) – An object to be inserted.
Raises:	IndexError: – This happens in one of the following cases: If the given index is out of the DoublyLinkedList() boundaries. If the given index is less than zero (-ve). TypeError: – This happens in one of the following cases: If the given index isn’t integer. If the given item is an instance of Extra. ValueError: – If the given item is None.

Example

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll.insert(1, 10)
>>> dll
 ┌───┐ ┌────┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 10 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └────┘ └───┘ └───┘
>>> dll.insert(5, item=8)
IndexError: Given index is out of the boundaries!!
>>> dll.insert(1, item=None)
ValueError: Can't use `None` as an element within         `extra.DoublyLinkedList()`!!
>>> dll.insert(-1, item=100)
IndexError: Negative indexing isn't supported with this functinoality!!

is_empty()¶

Checks if DoublyLinkedList() instance is an empty instance or not in constant time.

Returns:	A boolean flag showing if the DoublyLinkedList() instance is empty or not. True shows that this instance is empty and False shows it’s not empty.
Return type:	bool

Example

>>> dll = DoublyLinkedList()
>>> dll.is_empty()
True
>>> dll.add_front(5)
>>> dll.is_empty()
False

remove(value, all=True)¶

Removes a single node or multiple nodes (in case of all being True) whose value equal to the given value from the DoublyLinkedList() instance.

Parameters:	value (object) – The value to be removed from the DoublyLinkedList() instance. all (bool) – A flag (default: True); if True, all occurrences of the given value are remove. If False, only the first occurrence is removed.
Raises:	ValueError: – If The given value is None. TypeError: – This get raised in one of the following cases: If the type of the all flag isn’t boolean. If the given value is an instance of Extra class.

Example

>>> dll = DoublyLinkedList([1, 2, 3, 2, 2])
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 2 │⟷│ 2 │⟷
 └───┘ └───┘ └───┘ └───┘ └───┘
>>> dll.remove(2, all=False)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 3 │⟷│ 2 │⟷│ 2 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> dll.remove(10) #does nothing
>>> dll.remove(2)
>>> dll
 ┌───┐ ┌───┐
⟷│ 1 │⟷│ 3 │⟷
 └───┘ └───┘

remove_end()¶

Removes the value at the tail of the DoublyLinkedList() instance in constant time.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll.remove_end()
>>> dll
 ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷
 └───┘ └───┘
>>> dll.remove_end()
>>> dll
 ┌───┐
⟷│ 1 │⟷
 └───┘

remove_front()¶

Removes the value at the head of the DoublyLinkedList() instance in constant time.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll.remove_front()
>>> dll
 ┌───┐ ┌───┐
⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘
>>> dll.remove_front()
>>> dll
 ┌───┐
⟷│ 3 │⟷
 └───┘

reverse()¶

Reverses the whole DoublyLinkedList() instance in time-complexity of O(n) where n is the number of elements in the DoublyLinkedList().

Returns:	The reversed DoublyLinkedList() instance.
Return type:	DoublyLinkedList()

Example

>>> dll = DoublyLinkedList([1, 2, 3, 4])
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> dll.reverse()
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 4 │⟷│ 3 │⟷│ 2 │⟷│ 1 │⟷
 └───┘ └───┘ └───┘ └───┘

rotate_left(distance, inplace=True)¶

Rotates the DoublyLinkedList() instance to the left by a certain given distance. If inplace=True, it does the rotation in-place. If not, it returns the rotated instance. The time-compelxity of this method is of O(min(k,n/2)) where k is the index and n is the number of elements in the DoublyLinkedList() instance.

Parameters:	distance (int) – The rotation distance to the left. inplace (bool) – A flag to determine if the rotation is going to be in-place or not. (default True).
Returns:	The rotated instance if inplace=True and None if inplace=False.
Return type:	DoublyLinkedList()

Examples

>>> dll = DoublyLinkedList([1, 2, 3, 4])
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> dll.rotate_left(1)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷│ 1 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> # it works just fine when the distance is bigger than the
>>> # length of the doubly linked list instance
>>> dll.rotate_left(10)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 4 │⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘ └───┘

rotate_right(distance, inplace=True)¶

Rotates the DoublyLinkedList() instance to the right by a certain given distance. If inplace=True, it does the rotation in-place. If not, it returns the rotated instance. The time-compelxity of this method is O(min(k,n/2)) where k is the index and n is the number of elements in the original instance.

Parameters:	distance (int) – The rotation distance to the right. inplace (bool) – A flag to determine if the rotation is going to be in-place or not. (default True).
Returns:	The rotated instance if inplace=True
Return type:	DoublyLinkedList()

Examples

>>> dll = DoublyLinkedList([1, 2, 3, 4])
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> dll.rotate_right(1)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 4 │⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘ └───┘
>>> # it works just fine when the distance is bigger than the
>>> # length of the doubly linked list instance
>>> dll.rotate_right(14)
>>> dll
 ┌───┐ ┌───┐ ┌───┐ ┌───┐
⟷│ 2 │⟷│ 3 │⟷│ 4 │⟷│ 1 │⟷
 └───┘ └───┘ └───┘ └───┘

split(idx)¶

Splits the DoublyLinkedList() instance into two instances based on the given index in time-complexity of O(min(k,n/2)) where k is the index and n is the number of elements in the original instance. We can consider idx as the start index of the second DoublyLinkedList() after splitting. If idx=0, then the first returned DoublyLinkedList() will be empty while the second returned DoublyLinkedList() will be the same length as the original.

Parameters:	idx (int) – A positive integer pointing to the index at which the DoublyLinkedList() instance should be split.
Returns:	DoublyLinkedList() – The left DoublyLinkedList() instance returned after split. DoublyLinkedList() – The right DoublyLinkedList() instance returned after split
Raises:	TypeError: – If the given index isn’t int. IndexError: – If the given index is either negative or out of the boundaries of the DoublyLinkedList() instance.

Examples

>>> dll = DoublyLinkedList([1, 2, 3])
>>> dll
 ┌───┐ ┌───┐ ┌───┐
⟷│ 1 │⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘ └───┘
>>> left, right = dll.split(1)
>>> left
 ┌───┐
⟷│ 1 │⟷
 └───┘
>>> right
 ┌───┐ ┌───┐
⟷│ 2 │⟷│ 3 │⟷
 └───┘ └───┘

to_list()¶

Converts the DoublyLinkedList() instance to a list in time- complexity of O(n) where n is the number of elements in the instance.

Returns:	A list object containing the same elements as the DoublyLinkedList() instance.
Return type:	list

Example

>>> dll = DoublyLinkedList()
>>> dll.add_front(20)
>>> dll.add_front(10)
>>> dll.add_end(30)
>>> dll
 ┌────┐ ┌────┐ ┌────┐
⟷│ 10 │⟷│ 20 │⟷│ 30 │⟷
 └────┘ └────┘ └────┘
>>> dll.to_list()
[10, 20, 30]