Last active
August 16, 2021 04:20
-
-
Save e96031413/1435c22fd50a08d1547e1efe48f1b85b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Linked list implementation in Python | |
# https://www.programiz.com/dsa/linked-list | |
# Linked list operations in Python | |
# Create a node | |
class Node: | |
def __init__(self, data): | |
self.data = data | |
self.next = None | |
class LinkedList: | |
def __init__(self): | |
self.head = None | |
# Insert at the beginning | |
def insertAtBeginning(self, new_data): | |
new_node = Node(new_data) | |
new_node.next = self.head | |
self.head = new_node | |
# Insert after a node | |
def insertAfter(self, prev_node, new_data): | |
if prev_node is None: | |
print("The given previous node must inLinkedList.") | |
return | |
new_node = Node(new_data) | |
new_node.next = prev_node.next | |
prev_node.next = new_node | |
# Insert at the end | |
def insertAtEnd(self, new_data): | |
new_node = Node(new_data) | |
if self.head is None: | |
self.head = new_node | |
return | |
last = self.head | |
while (last.next): | |
last = last.next | |
last.next = new_node | |
# Deleting a node | |
def deleteNode(self, position): | |
if self.head is None: | |
return | |
temp = self.head | |
if position == 0: | |
self.head = temp.next | |
temp = None | |
return | |
# Find the key to be deleted | |
for i in range(position - 1): | |
temp = temp.next | |
if temp is None: | |
break | |
# If the key is not present | |
if temp is None: | |
return | |
if temp.next is None: | |
return | |
next = temp.next.next | |
temp.next = None | |
temp.next = next | |
# Search an element | |
def search(self, key): | |
current = self.head | |
while current is not None: | |
if current.data == key: | |
return True | |
current = current.next | |
return False | |
# Sort the linked list | |
def sortLinkedList(self, head): | |
current = head | |
index = Node(None) | |
if head is None: | |
return | |
else: | |
while current is not None: | |
# index points to the node next to current | |
index = current.next | |
while index is not None: | |
if current.data > index.data: | |
current.data, index.data = index.data, current.data | |
index = index.next | |
current = current.next | |
# Print the linked list | |
def printList(self): | |
temp = self.head | |
while (temp): | |
print(str(temp.data) + " ", end="") | |
temp = temp.next | |
if __name__ == '__main__': | |
llist = LinkedList() | |
llist.insertAtEnd(1) | |
llist.insertAtBeginning(2) | |
llist.insertAtBeginning(3) | |
llist.insertAtEnd(4) | |
llist.insertAfter(llist.head.next, 5) | |
print('linked list:') | |
llist.printList() | |
print("\nAfter deleting an element:") | |
llist.deleteNode(3) | |
llist.printList() | |
print() | |
item_to_find = 3 | |
if llist.search(item_to_find): | |
print(str(item_to_find) + " is found") | |
else: | |
print(str(item_to_find) + " is not found") | |
llist.sortLinkedList(llist.head) | |
print("Sorted List: ") | |
llist.printList() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment