Linked List

A 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 a reference to an object that is an element of the sequence, as well as a reference to the next node of the linked list.

The first node of a linked list is known as the head of the linked list. By starting at the linked list’s head and moving to the latter nodes using each node’s next reference, we can reach the end of the list. This process is commonly known as traversing the linked list.

../../_images/linked_list.gif

⏱ 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 linked list.
  • m is the number of elements in the other linked list.
  • k is the value of a given index.
Method Description Worst-case Optimal
is_empty() Checks if the linked list is empty. O(1) O(1)
__len__() Returns the number of nodes in the linked list. O(1) O(1)
__repr__() Represents the linked list as a string. O(n) O(n)
__iters__() Iterates over the linked list instance. O(n) O(n)
__eq__() Checks the items equality of the two linked lists. O(min(n;m)) O(min(n;m))
__ne__() Checks the items inequality of the two linked lists. O(min(n;m)) O(min(n;m))
__lt__() Checks if the linked list is less than the other. O(min(n;m)) O(min(n;m))
__le__() Checks if the list is less than or equal the other. O(min(n;m)) O(min(n;m))
__gt__() Checks if the linked list is greater than the other. O(min(n;m)) O(min(n;m))
__ge__() Checks if the list is greater than or equal the other. O(min(n;m)) O(min(n;m))
__contains__() Checks the existence of the given item in the list O(n) O(n)
__getitem__() Returns the element at the given index. O(k) O(k)
add_front() Adds the given item at the head of the linked list. O(1) O(1)
add_end() Adds the given item at the tail of the linked list. O(n) O(n)
insert() Adds the given item at the given index. O(k) O(k)
__setitem__() Replaces the value at the given index with given value. O(k) O(k)
__delitem__() Deletes the value at the given index. O(n) O(n)
remove_front() Removes the node at the head of the linked list. O(1) O(1)
remove_end() Removes the node at the tail of the linked list. O(n) O(n)
remove() Removes the given value from the linked list if found. O(n) O(n)
clear() Clears the whole linked list. O(1) O(1)
split() Splits the linked list into two at the given index. O(n) O(n)
extend() Extends the linked list using another linked list. O(n) O(n)
rotate_left() Left-rotates the linked list a given number of times. O(k%n) O(k%n)
rotate_right() Right-rotates the linked list a given number of times. O(k%n) O(k%n)
reverse() Reverses the linked list. O(n) O(n)
to_list() Converts the linked list to a normal list. O(n) O(n)
count() Counts the occurrences of the given value in the list. O(n) O(n)
copy() Shallow-copies the linked list. O(n) O(n)

☕️ API

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

class extra.lists.linked_list.LinkedList(iterable=None)

A 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 a reference to an object that is an element of the sequence, as well as a reference to the next node of the linked list.

__contains__(value)

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

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

Examples

>>> ll = LinkedList([1, 3, 5])
>>> 1 in ll
True
>>> 0 in ll
False
>>> "hello" in ll
False
__delitem__(idx)

Deletes the value at the given index in the LinkedList() instance. It does that in time-complexity of O(k) where k is the index value.

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

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

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

  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 (LinkedList()) – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 3, 2])
>>> ll_1 == ll_2
False
>>> ll_1 == ll_1
True
__ge__(other)

Checks if the first LinkedList() 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:LinkedList() – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 3, 5])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 >= ll_2
True
>>> ll_1 = LinkedList([1, 3, 2, 1])
>>> ll_2 = LinkedList([1, 3, 2])
>>> ll_1 >= ll_2
True
>>> ll_1 = LinkedList([1, 2])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 >= ll_2
False
>>> ll_1 = LinkedList([5, 2, 1])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 >= ll_2
False
>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 2, 3])
>>> ll_1 >= ll_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 as well. 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 LinkedList() instance.

Returns:

If the given index is an int, then it returns the value at that index. If the given index is a slice object, then it returns a LinkedList() instance containing the desired values.

Return type:

object or LinkedList()

Raises:
  • TypeError: – If the given index isn’t int.
  • IndexError: – If the given index is out of the LinkedList() boundaries.

Examples

>>> ll = LinkedList([1, 2, 3, 4, 5])
>>> ll[0]
1
>>> ll[-2]
4
>>> ll[2:]
┌───┐ ┌───┐ ┌───┐
│ 3 │⟶│ 4 │⟶│ 5 │⟶
└───┘ └───┘ └───┘
>>> ll[0:5:2]
┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 3 │⟶│ 5 │⟶
└───┘ └───┘ └───┘
>>> ll[10]
IndexError: Given index is out of the boundaries!!
__gt__(other)

Checks if the first LinkedList() 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:LinkedList() – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 3, 5])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 > ll_2
True
>>> ll_1 = LinkedList([1, 3, 2, 1])
>>> ll_2 = LinkedList([1, 3, 2])
>>> ll_1 > ll_2
True
>>> ll_1 = LinkedList([1, 2])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 > ll_2
False
>>> ll_1 = LinkedList([5, 2, 1])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 > ll_2
False
>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 2, 3])
>>> ll_1 > ll_2
False
__init__(iterable=None)

Initializes a LinkedList() object 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 (any iterable object, optional.) – An iterable object that implements the __iter__ method. For example, list and tuple are both iterables.

Raises:
  • TypeError – It can be raised in two cases:
    1. In case the given object isn’t iterable.
    2. If one of the iterable elements is an Extra object.
  • ValueError – If one of the iterable elements has None as a value.

Examples

>>> ll = LinkedList([10, -5, 7, 9])
>>> ll
┌────┐ ┌────┐ ┌───┐ ┌───┐
│ 10 │⟶│ -5 │⟶│ 7 │⟶│ 9 │⟶
└────┘ └────┘ └───┘ └───┘

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

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

Using a non-iterable object will raise TypeError

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

Using nested LinkedList objects will raise TypeError as well

>>> ll_1 = LinkedList([1])
>>> ll_2 = LinkedList([1, ll_1])
TypeError: Can't use `extra.LinkedList()` with `extra.LinkedList()`!!

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 Linked List just like so:

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

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

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

Examples

>>> ll = LinkedList([1, 2, 3])
>>> for item in ll:
...     print(item)
1
2
3
__le__(other)

Checks if the first LinkedList() 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:LinkedList() – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 3, 2])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 <= ll_2
True
>>> ll_1 = LinkedList([1, 3])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 <= ll_2
True
>>> ll_1 = LinkedList([1, 5])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 <= ll_2
False
>>> ll_1 = LinkedList([5, 2, 1])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 <= ll_2
False
>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 2, 3])
>>> ll_1 <= ll_2
True
__len__()

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

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

Examples

>>> ll = LinkedList()
>>> len(ll)
0
>>> ll = LinkedList((2, 5, 0))
>>> len(ll)
3
__lt__(other)

Checks if the first LinkedList() 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:LinkedList() – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 3, 2])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 < ll_2
True
>>> ll_1 = LinkedList([1, 3])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 < ll_2
True
>>> ll_1 = LinkedList([1, 5])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 < ll_2
False
>>> ll_1 = LinkedList([5, 2, 1])
>>> ll_2 = LinkedList([1, 3, 3])
>>> ll_1 < ll_2
False
>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 2, 3])
>>> ll_1 < ll_2
False
__ne__(other)

Checks if two LinkedList() 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 (LinkedList()) – 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 LinkedList() instance. 2. In case one element in the first instance doesn’t match the type of the opposing element in the other instance.

Examples

>>> ll_1 = LinkedList([1, 2, 3])
>>> ll_2 = LinkedList([1, 3, 2])
>>> ll_1 != ll_2
True
>>> ll_1 != ll_1
False
__repr__()

Represents the LinkedList() instance as a string.

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

Example

>>> ll = LinkedList([20, 77, 10, 6, 2])
>>> ll
┌────┐ ┌────┐ ┌────┐ ┌───┐ ┌───┐
│ 20 │⟶│ 77 │⟶│ 10 │⟶│ 6 │⟶│ 2 │⟶
└────┘ └────┘ └────┘ └───┘ └───┘
__setitem__(idx, item)

Replaces the value at the given index in the LinkedList() instance with the given item. It does that in time-complexity of O(k) where k is the index value.

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:
    1. If the given index type is not int.
    2. If the given object is an instance of Extra.

Examples

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

Adds the given value at the tail of the LinkedList() instance in linear time.

Parameters:

item (object) – The value to be inserted at the LinkedList() tail.

Raises:
  • TypeError: – If the given item is an instance of Extra.
  • ValueError: – If the given item is None.

Examples

>>> ll = LinkedList([1, 2, 3])
>>> ll.add_end(10)
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌────┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶│ 10 │⟶
└───┘ └───┘ └───┘ └────┘
add_front(item)

Adds the given item at the head of the LinkedList() instance in contant time.

Parameters:

item (object) – The value to be inserted at the head of the LinkedList().

Raises:
  • TypeError: – If the given item is an instance of Extra.
  • ValueError: – If the given item is None.

Examples

>>> ll = LinkedList([1, 2, 3])
>>> ll.add_front(10)
>>> ll
┌────┐ ┌───┐ ┌───┐ ┌───┐
│ 10 │⟶│ 1 │⟶│ 2 │⟶│ 3 │⟶
└────┘ └───┘ └───┘ └───┘
clear()

Removes all nodes within the LinkedList() instance in constant time.

Example

>>> ll = LinkedList([1, 2, 3])
>>> ll
┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶
└───┘ └───┘ └───┘
>>> ll.clear()
>>> ll.is_empty()
True
>>> ll
┌─

└─
copy()

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

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

Example

>>> ll = LinkedList()
>>> ll.add_end(10)
>>> ll.add_end(20)
>>> ll
┌────┐ ┌────┐
│ 10 │⟶│ 20 │⟶
└────┘ └────┘
>>> ll.copy()
┌────┐ ┌────┐
│ 10 │⟶│ 20 │⟶
└────┘ └────┘
count(value)

Counts the number of occurrences of the given value in the LinkedList() instance.

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

Example

>>> ll = LinkedList([0, 1, 1, 2, 3, 5])
>>> ll.count(3)
1
>>> ll.count(1)
2
>>> ll.count("he")
0
extend(other)

Extends the current LinkedList() instance by appending the elements of the other LinkedList() instance in time-complexity of O(n) where n is the lengh of the current instance.

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

Example

>>> ll_1 = LinkedList([1, 2])
>>> ll_2 = LinkedList([3, 4, 5])
>>> ll_1
┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶
└───┘ └───┘
>>> ll_1.extend(ll_2)
>>> ll_1
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶│ 4 │⟶│ 5 │⟶
└───┘ └───┘ └───┘ └───┘ └───┘
>>> ll_1.extend([6, 7])
TypeError: Type Mismatch! Can't extend `extra.LinkedList()` with
`<class 'list'>`!!
insert(idx, item)

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

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:
    1. If the given index is out of the LinkedList() boundaries.
    2. If the given index is less than zero (-ve).
  • TypeError: – This happens in one of the following cases:
    1. If the given index isn’t integer.
    2. If the given item is an instance of Extra.
  • ValueError: – If the given item is None.

Example

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

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

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

Example

>>> ll = LinkedList()
>>> ll.is_empty()
True
>>> ll.add_front(5)
>>> ll.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 LinkedList() instance.

Parameters:
  • value (object) – The value to be removed from the LinkedList() 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:
    1. If the type of the all flag isn’t boolean.
    2. If the given value is an instance of Extra class.

Example

>>> ll = LinkedList([1, 2, 3, 2, 2])
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶│ 2 │⟶│ 2 │⟶
└───┘ └───┘ └───┘ └───┘ └───┘
>>> ll.remove(2, all=False)
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 3 │⟶│ 2 │⟶│ 2 │⟶
└───┘ └───┘ └───┘ └───┘
>>> ll.remove(10) #does nothing
>>> ll.remove(2)
>>> ll
┌───┐ ┌───┐
│ 1 │⟶│ 3 │⟶
└───┘ └───┘
remove_end()

Removes the value at the tail of the LinkedList() instance in time- complexity of O(n) where n is the number of elements in the LinkedList() instance.

Examples

>>> ll = LinkedList([1, 2, 3])
>>> ll.remove_end()
>>> ll
┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶
└───┘ └───┘
>>> ll.remove_end()
>>> ll
┌───┐
│ 1 │⟶
└───┘
remove_front()

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

Examples

>>> ll = LinkedList([1, 2, 3])
>>> ll.remove_front()
>>> ll
┌───┐ ┌───┐
│ 2 │⟶│ 3 │⟶
└───┘ └───┘
>>> ll.remove_front()
>>> ll
┌───┐
│ 3 │⟶
└───┘
reverse()

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

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

Example

>>> ll = LinkedList([1, 2, 3, 4])
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶│ 4 │⟶
└───┘ └───┘ └───┘ └───┘
>>> ll.reverse()
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 4 │⟶│ 3 │⟶│ 2 │⟶│ 1 │⟶
└───┘ └───┘ └───┘ └───┘
rotate_left(distance, inplace=True)

Rotates the LinkedList() instance to the left by a number of times defined by the 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(n) where n is the number of elements in the original LinkedList() 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

Return type:

LinkedList()

Examples

>>> ll = LinkedList([1, 2, 3, 4])
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶│ 4 │⟶
└───┘ └───┘ └───┘ └───┘
>>> ll.rotate_left(1)
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 2 │⟶│ 3 │⟶│ 4 │⟶│ 1 │⟶
└───┘ └───┘ └───┘ └───┘
>>> # it works just fine when the distance is bigger than the
>>> # length of the linked list instance
>>> ll.rotate_left(10)
>>> ll
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 3 │⟶│ 4 │⟶│ 1 │⟶│ 2 │⟶
└───┘ └───┘ └───┘ └───┘
rotate_right(distance, inplace=True)

Rotates the LinkedList() instance to the right by a number of times defined by the 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(n) where n is the number of elements in the original LinkedList() 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:

LinkedList()

Examples

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

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

Parameters:

idx (int) – A positive integer pointing to the index at which the LinkedList()` instance should be split.

Returns:

  • LinkedList() – The left LinkedList() instance returned after split.
  • LinkedList() – The right LinkedList() 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 LinkedList() boundaries.

Examples

>>> ll = LinkedList([1, 2, 3])
>>> ll
┌───┐ ┌───┐ ┌───┐
│ 1 │⟶│ 2 │⟶│ 3 │⟶
└───┘ └───┘ └───┘
>>> left, right = ll.split(1)
>>> left
┌───┐
│ 1 │⟶
└───┘
>>> right
┌───┐ ┌───┐
│ 2 │⟶│ 3 │⟶
└───┘ └───┘
to_list()

Converts the LinkedList() 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 LinkedList() instance.
Return type:list

Example

>>> ll = LinkedList()
>>> ll.add_front(20)
>>> ll.add_front(10)
>>> ll.add_end(30)
>>> ll
┌────┐ ┌────┐ ┌────┐
│ 10 │⟶│ 20 │⟶│ 30 │⟶
└────┘ └────┘ └────┘
>>> ll.to_list()
[10, 20, 30]