The LinkedList package offers a robust and efficient implementation of a singly linked list data structure in Python. Unlike raw linked lists, this package provides convenient access to elements using indices, allowing for seamless integration with Python's iterable features, such as for loops and other iterable functions. With this package, you can create linked lists and effortlessly access and modify their elements just like you would with lists or tuples.
The primary goal of this package is to bridge the gap between raw linked lists and Python's built-in data structures, making linked lists as user-friendly and versatile as possible. By using this package, you can harness the power of linked lists while enjoying the familiar functionalities offered by Python's native data structures.
- Project Architecture
- Features
- Installation
- Usage
- Contributing
- License
WORKSPACE /
|
|--> LinkedList /
| |
| |--> __init__.py
| |
| |--> base_list.py
| |
| |--> node.py
| |
| |--> linked_list.py
|
|--> tests /
| |
| |--> linked_list_test.py
|
|--> .gitignore
|
|--> LICENSE
|
|--> logo.png
|
|--> README.md
|
|--> requirements.txt
|
|--> setup.py
Here are some key features of LinkedList provided by this package :
- Create a new linked list.
- Setting element with indexing.
- Print linked list using print function.
- Insert element in an existing linked list.
- Get the length of the linked list and reverse it.
- Sort the linked list in ascending or descending order.
- Delete elements(Nodes) from the linked list (using index).
- Perform concatenation of two or more LinkedLists (using '+').
- Insert element in an existing linked list at any index of linked list.
- Access and update elements using index (Just like noraml list in python).
- Perform element-wise division with a numeric value (for numeric linked list).
- Perform element-wise multiplication with a numeric value (for numeric linked list).
You can install LinkedList package using pip :
pip install LinkedList_575The linked list is present in linked_list.py file of LinkedList package. To use linked list in your project, you needed to import. You can import it as follows ;
from LinkedList.linked_list import LinkedListNow , let's create an object of linked list using LinkedList module. It will create an empty linked list :
linked_list = LinkedList()We have created an empty linked list. Now , we can add elements using insert() method :
linked_list.insert(10) # Append 10 at the end
linked_list.insert(30, 1) # Inserts 30 at index 1
linked_list.insert(20, 0) # Inserts 20 at the beginning
linked_list.insert(40,-1) # Inserts 40 at index -1 (last position)
linked_list.insert(-8,-2) # Inserts -8 at index -2 (second last position)Now we can print each node of linked_list just using print function :
print(linked_list) # output : 20 --> 10 --> 30 --> -8 --> 40 --> NoneNow we can access each elements of linked_list present at any node using its index(i.e writing index in square braces) as we are accessing in case of normal list in python :
print(linked_list[2]) # Output: 30 (Value at index 2)
print(linked_list[-1]) # Output: 40 (Value of the last element)
print(linked_list[-2]) # Output: -8 (Value of the second last element)
print(linked_list[0]) # Output: 20 (Value at index 0, i.e value of the first element)
print(linked_list[-4]) # Output: 10 (Value at index -4, i.e., value of the fourth last element)
n = len(linked_list) # Getting length of linked_list
for i in range(n) :
print(linked_list[i])
# output:
# 20
# 10
# 30
# -8
# 40As we know that it is very convinient to use and access the element of data structure by using for loop. But in case of linked list we can not directly access elements(data present at the node) using for loop. To solve this problem, I have used __iter__ and __next__ dunder method to make it irerable.
for data in linked_list :
print(data)
# Output:
# 20
# 10
# 30
# -8
# 40Now we can update each elements of linked_list present at any node using its index(i.e writing index in square braces) and assignment as we are updating in case of normal list in python :
linked_list[-1] = 25 # Update element at index -1 (i.e last element) to 25
linked_list[2] = 50 # Update element at index 2 (i.e third element) to 50
linked_list[0] = 108 # Update element at index 0 (i.e fist element) to 108
linked_list[-2] = -9 # Update element at index -2 (i.e second last element) to -9
linked_list[-4] = 0 # Update element at index -4 (i.e value of the fourth last element) to 0Now , let's see the updated linked_list :
print(linked_list) # output: 108 --> 0 --> 50 --> -9 --> 25 --> NoneWe can perform concatenation operation of two or more linked lists by just using '+' operator between them, let's see the example ;
linked_list1 = LinkedList() # Create linked list
linked_list2 = LinkedList() # Create linked list
# Let's add the elements to both the linked lists
for i in range(6) :
linked_list1.insert(i , 0)
for i in range(5) :
linked_list2.insert(-(i+1) , 0)# Let's print both the linked lists
print('linked_list1 =' ,linked_list1) # output: linked_list1 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> None
print('linked_list2 =' ,linked_list2) # output: linked_list2 = -5 --> -4 --> -3 --> -2 --> -1 --> None# Let's perform concatenation of two linked lists linked_list1 and linked_list2
result1 = linked_list1 + linked_list2
result2 = linked_list2 + linked_list1# Now, let's print concatenated linked list
print('result1 =' , result1) # output: result1 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> -5 --> -4 --> -3 --> -2 --> -1 --> None
print('result2 =' , result2) # output: result2 = -5 --> -4 --> -3 --> -2 --> -1 --> 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> None# Let's perform concatenation of more than two linked lists
result3 = linked_list1 + linked_list2 + linked_list
# Now, let's print result3
print('result3 =' , result3) # output: result3 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> -5 --> -4 --> -3 --> -2 --> -1 --> 108 --> 0 --> 50 --> -9 --> 25 --> NoneIn this section, we will perform some basic operations in linked list like finding length , reversing the node and sorting etc.
As in case of python list or tuple or any other iterable it is an important task to find the number of elements present in the data structure. As finding the number of elements can be very important insight of data structure like we can iterate over the length and so on. We can find the number of elements by using len() funtion and we can pass linked list as as argument. This function len() will return the number of elements present in the linked list or we can say that it is a length of linked list.
# Finding length of linked lists
print(len(linked_list )) # output: 5
print(len(linked_list1)) # output: 6
print(len(linked_list2)) # output: 5
print(len(result1)) # output: 11
print(len(result2)) # output: 11
print(len(result3)) # output: 16We have performed reverse operations many time in case of python iterables like list or tuple. Similarly, we can use the same function that is reversed() to reverse node of linked list. In this function reverse() we need to pass linked list as an argument.
# Reversing nodes of linked lists
print('Before reversing : linked_list =' , linked_list) # output: Before reversing : linked_list = 108 --> 0 --> 50 --> -9 --> 25 --> None
reversed(linked_list)
print('After reversing : linked_list =' , linked_list) # output: After reversing : linked_list = 25 --> -9 --> 50 --> 0 --> 108 --> Noneprint('Before reversing : linked_list1 =' ,linked_list1) # output: Before reversing : linked_list1 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> None
reversed(linked_list1)
print('After reversing : linked_list1 =' ,linked_list1) # output: After reversing : linked_list1 = 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> Noneprint('Before reversing : linked_list2 =' ,linked_list2) # output: Before reversing : linked_list2 = -5 --> -4 --> -3 --> -2 --> -1 --> None
reversed(linked_list2)
print('After reversing : linked_list2 =' ,linked_list2) # output: After reversing : linked_list2 = -1 --> -2 --> -3 --> -4 --> -5 --> Noneprint('Before reversing : result1 =' , result1) # output: Before reversing : result1 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> -5 --> -4 --> -3 --> -2 --> -1 --> None
reversed(result1)
print('After reversing : result1 =' , result1) # output: After reversing : result1 = -1 --> -2 --> -3 --> -4 --> -5 --> 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> Noneprint('Before reversing : result2 =' , result2) # output: Before reversing : result2 = -5 --> -4 --> -3 --> -2 --> -1 --> 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> None
reversed(result2)
print('After reversing : result2 =' , result2) # output: After reversing : result2 = 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> -1 --> -2 --> -3 --> -4 --> -5 --> Noneprint('Before reversing : result3 =' , result3) # output: Before reversing : result3 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> -5 --> -4 --> -3 --> -2 --> -1 --> 108 --> 0 --> 50 --> -9 --> 25 --> None
reversed(result3)
print('After reversing : result3 =' , result3) # output: After reversing : result3 = 25 --> -9 --> 50 --> 0 --> 108 --> -1 --> -2 --> -3 --> -4 --> -5 --> 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> NoneWe know that in numpy we can multilpy or divide array(numeric) with any numeric value, as a result the we will get an array in which all the elements of numpy array will be multiplied or divided by the number we have provided. Same operation can be performed on this LinkedList
# Multiplying Linked List by any numeric value
print('Before multiplication : linked_list =' , linked_list) # output: Before multiplication : linked_list = 25 --> -9 --> 50 --> 0 --> 108 --> None
linked_list*2
print('After multiplication : linked_list =' , linked_list) # output: After multiplication : linked_list = 50 --> -18 --> 100 --> 0 --> 216 --> None# Dividing Linked List by any numeric value
print('Before division : linked_list =' , linked_list) # output: After division : linked_list = 50 --> -18 --> 100 --> 0 --> 216 --> None
linked_list / 2
print('After division : linked_list =' , linked_list) # output: After division : linked_list = 25.0 --> -9.0 --> 50.0 --> 0.0 --> 108.0 --> NoneSorting is one of the most important part in case of oterables. As we have many options to sort LinkedList. But, here we will use merge sort that will provide time complexity of nlog(n) and space complexity is constant.
print('Before sorting : linked_list2 =' , linked_list2) # output: After sorting : linked_list2 = -1 --> -2 --> -3 --> -4 --> -5 --> None
linked_list2.sort()
print('After sorting : linked_list2 =' , linked_list2) # output: After sorting : linked_list2 = -5 --> -4 --> -3 --> -2 --> -1 --> Noneprint('Before sorting : linked_list1 =' , linked_list1) # output: After sorting : linked_list1 = 0 --> 1 --> 2 --> 3 --> 4 --> 5 --> None
linked_list1.sort(reverse = True)
print('After sorting : linked_list1 =' , linked_list1) # output: After sorting : linked_list1 = 5 --> 4 --> 3 --> 2 --> 1 --> 0 --> NoneContributions to the LinkedList package are welcome! If you find any bugs or have suggestions for improvement, please open an issue or submit a pull request on GitHub.
© 2023 Saqib Shaikh
This package is distributed under the GNU General Public License v3.0 (GPLv3) License. See the LICENSE file for more details.