-
Notifications
You must be signed in to change notification settings - Fork 0
/
Custom-Built Linked List.py
149 lines (132 loc) · 4.82 KB
/
Custom-Built Linked List.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# create node class with basic features: data and reference pointer
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def __str__(self):
return f"{self.data}"
# create basic linkedlist which we will be tracking both the head and tail
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
#funtion for adding nodes to end of list
def append_value(self, value):
if not isinstance(value, Node): # this checks if value passed is a node or not.
value = Node(value)
if self.head == None: # checks if head node is empty to indicate empty list or not
self.head = value
else:
self.tail.next = value
self.tail = value
def __str__(self):
output = ""
current = self.head
while current is not None:
output += str(current.data) + "->"
current = current.next
if output:
return "[" + output[:-2] + "]"
return "[]"
# function to add nodes to beginning of linked list
def left_append_value(self, value):
if not isinstance(value, Node):
value = Node(value)
if self.head == None:
self.head = value
else:
old = self.head
self.head = value
self.head.next = old # references head pointer to the previous head value
# function to search for node in list by passing index as parameter
def search_value(self, index):
current = self.head
position = 0
while position != index:
current = current.next
position += 1
if position == index:
return f"{current.data} found at index {index}"
else:
return f"No value at index {index}"
# function to remove node from list by passing index as parameter.
def remove_value(self, index):
current = self.head
position = 0
while position != index:
last = current
current = current.next
position += 1
if position == index:
last.next = current.next
return
# function to determine length of linked list.
def length_list(self):
length = 0
current = self.head
while current is not None:
current = current.next
length += 1
return f"length of linked list is {length}"
# EXTRA FEATURE- WITH UPCOMING APPLICATIONS (palidrome, etc).
# This function reverses list recursively.
def reverse_list_recursively(self, current, previous):
if self.head == None: # checks for empty list
return
elif current.next == None: # checks if at last node in list
self.tail = self.head
current.next = previous # references the pointer of the current node to the previous instead of the next one.
self.head = current # sets current (last node) as head
else:
next = current.next # stores value of next node (node to the right of current) in a variable
current.next = previous # sets pointer of current node to previous node instead of next
self.reverse_list_recursively(next, current)
# This function converts non-empty linked lists to integer value
def convert_linkedlist_to_value(self):
arr=[]
arr_val=""
current = self.head
while current != None:
arr.append(int(current.data))
current = current.next
for i in arr:
arr_val= str(i) + arr_val
return int(arr_val)
# This function adds two non-empty linked list represented as integer values.
def add_two_numbers(self, value1, value2):
#value1=self.convert_list_to_value()
value1=Node(value1)
#value2=self.convert_list_to_value()
value2=Node(value2)
result = []
total = str(value1.data + value2.data)
for i in total:
result.append(int(i))
for num in result:
self.left_append(num)
my_list = LinkedList()
#my_list.append_value(1)
#my_list.append_value(2)
#my_list.append_value(3)
#my_list.append_value(4)
#my_list.append_value(5)
#print(my_list)
#my_list.left_append_value(6)
#print(my_list.length_list())
#print(my_list.search_value(2))
#print(my_list.remove_value(3))
print(my_list)
my_list1 = LinkedList()
my_list1.append_value(2)
my_list1.append_value(4)
my_list1.append_value(3)
value1=my_list1.convert_list_to_value()
my_list2 = LinkedList()
my_list2.append_value(5)
my_list2.append_value(6)
my_list2.append_value(4)
value2=my_list2.convert_list_to_value()
my_list.add_two_numbers(value1, value2)
print(my_list)
#my_list.reverse_list_recursively(my_list.head, None)
#print(my_list)