1class Node:
2 def __init__(self, data = None, next_node = None):
3 self.data = data
4 self.nextNode = next_node
5
6 def get_data(self):
7 return self.data
8
9 def set_data(self, data):
10 self.data = data
11
12 def get_nextNode(self):
13 return self.nextNode
14
15 def set_nextNode(self, nextNode):
16 self.nextNode = nextNode
17
18
19class LinkedList:
20 def __init__(self, head = None):
21 self.head = head
22
23
24 def add_Node(self, data):
25 # if empty
26 if self.head == None:
27 self.head = Node(data)
28
29
30 # not empty
31 else:
32 curr_Node = self.head
33
34 # if node added is at the start
35 if data < curr_Node.get_data():
36 self.head = Node(data, curr_Node)
37
38 # not at start
39 else:
40 while data > curr_Node.get_data() and curr_Node.get_nextNode() != None:
41 prev_Node = curr_Node
42 curr_Node = curr_Node.get_nextNode()
43
44 # if node added is at the middle
45 if data < curr_Node.get_data():
46 prev_Node.set_nextNode(Node(data, curr_Node))
47
48
49 # if node added is at the last
50 elif data > curr_Node.get_data() and curr_Node.get_nextNode() == None:
51 curr_Node.set_nextNode(Node(data))
52
53
54
55 def search(self, data):
56 curr_Node = self.head
57 while curr_Node != None:
58 if data == curr_Node.get_data():
59 return True
60
61 else:
62 curr_Node = curr_Node.get_nextNode()
63
64 return False
65
66
67 def delete_Node(self, data):
68 if self.search(data):
69 # if data is found
70
71 curr_Node = self.head
72 #if node to be deleted is the first node
73 if curr_Node.get_data() == data:
74 self.head = curr_Node.get_nextNode()
75
76 else:
77 while curr_Node.get_data() != data:
78 prev_Node = curr_Node
79 curr_Node = curr_Node.get_nextNode()
80
81 #node to be deleted is middle
82 if curr_Node.get_nextNode() != None:
83 prev_Node.set_nextNode(curr_Node.get_nextNode())
84
85 # node to be deleted is at the end
86 elif curr_Node.get_nextNode() == None:
87 prev_Node.set_nextNode(None)
88
89 else:
90 return "Not found."
91
92 def return_as_lst(self):
93 lst = []
94 curr_Node = self.head
95 while curr_Node != None:
96 lst.append(curr_Node.get_data())
97 curr_Node = curr_Node.get_nextNode()
98
99 return lst
100
101 def size(self):
102 curr_Node = self.head
103 count = 0
104 while curr_Node:
105 count += 1
106 curr_Node = curr_Node.get_nextNode()
107 return count
108
109
110## TEST CASES #
111test1 = LinkedList()
112test2 = LinkedList()
113test1.add_Node(20)
114test1.add_Node(15)
115test1.add_Node(13)
116test1.add_Node(14)
117test1.delete_Node(17)
118print(test1.return_as_lst())
119print(test2.size())
1# Linked list operations in Python
2
3
4# Create a node
5class Node:
6 def __init__(self, data):
7 self.data = data
8 self.next = None
9
10
11class LinkedList:
12
13 def __init__(self):
14 self.head = None
15
16 # Insert at the beginning
17 def insertAtBeginning(self, new_data):
18 new_node = Node(new_data)
19
20 new_node.next = self.head
21 self.head = new_node
22
23 # Insert after a node
24 def insertAfter(self, prev_node, new_data):
25
26 if prev_node is None:
27 print("The given previous node must inLinkedList.")
28 return
29
30 new_node = Node(new_data)
31 new_node.next = prev_node.next
32 prev_node.next = new_node
33
34 # Insert at the end
35 def insertAtEnd(self, new_data):
36 new_node = Node(new_data)
37
38 if self.head is None:
39 self.head = new_node
40 return
41
42 last = self.head
43 while (last.next):
44 last = last.next
45
46 last.next = new_node
47
48 # Deleting a node
49 def deleteNode(self, position):
50
51 if self.head is None:
52 return
53
54 temp = self.head
55
56 if position == 0:
57 self.head = temp.next
58 temp = None
59 return
60
61 # Find the key to be deleted
62 for i in range(position - 1):
63 temp = temp.next
64 if temp is None:
65 break
66
67 # If the key is not present
68 if temp is None:
69 return
70
71 if temp.next is None:
72 return
73
74 next = temp.next.next
75
76 temp.next = None
77
78 temp.next = next
79
80 # Search an element
81 def search(self, key):
82
83 current = self.head
84
85 while current is not None:
86 if current.data == key:
87 return True
88
89 current = current.next
90
91 return False
92
93 # Sort the linked list
94 def sortLinkedList(self, head):
95 current = head
96 index = Node(None)
97
98 if head is None:
99 return
100 else:
101 while current is not None:
102 # index points to the node next to current
103 index = current.next
104
105 while index is not None:
106 if current.data > index.data:
107 current.data, index.data = index.data, current.data
108
109 index = index.next
110 current = current.next
111
112 # Print the linked list
113 def printList(self):
114 temp = self.head
115 while (temp):
116 print(str(temp.data) + " ", end="")
117 temp = temp.next
118
119
120if __name__ == '__main__':
121
122 llist = LinkedList()
123 llist.insertAtEnd(1)
124 llist.insertAtBeginning(2)
125 llist.insertAtBeginning(3)
126 llist.insertAtEnd(4)
127 llist.insertAfter(llist.head.next, 5)
128
129 print('linked list:')
130 llist.printList()
131
132 print("\nAfter deleting an element:")
133 llist.deleteNode(3)
134 llist.printList()
135
136 print()
137 item_to_find = 3
138 if llist.search(item_to_find):
139 print(str(item_to_find) + " is found")
140 else:
141 print(str(item_to_find) + " is not found")
142
143 llist.sortLinkedList(llist.head)
144 print("Sorted List: ")
145 llist.printList()
1Full Linked List implementation at this link:
2https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/LinkedList
1class LinkedList(object):
2 def __init__(self, head=None):
3 self.head = head
4
5 # ignored... answer below
6 def get_position(self, position):
7 counter = 1
8 current = self.head
9 if position < 1:
10 return None
11 while current and counter <= position:
12 if counter == position:
13 return current
14 current = current.next
15 counter += 1
16 return None
17 # ignored... answer above
181234567891011121314151617
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
5
6 def __repr__(self):
7 return self.data
8
9class LinkedList:
10 def __init__(self):
11 self.head = None
12
13 def __repr__(self):
14 node = self.head
15 nodes = []
16 while node is not None:
17 nodes.append(node.data)
18 node = node.next
19 nodes.append("None")
20 return " -> ".join(nodes)
21