-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedList.py
130 lines (94 loc) · 2.7 KB
/
LinkedList.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
class Node():
def __init__(self, value, next, previous):
self._value = value
self._next = next
self._previous = previous
class LinkedList():
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def append(self, value):
# Empty LinkedList
if self.length == 0:
self.head = Node(value, None, None)
self.tail = self.head
elif self.length == 1:
# 1 element LinkedList
self.tail = Node(value, None, self.head)
self.head._next = self.tail
elif self.length > 1:
# More than 1 element LinkedList
new_node = Node(value, None, self.tail)
self.tail._next = new_node
self.tail = new_node
self.length += 1
def prepend(self, value):
# Empty LinkedList
if self.length == 0:
self.head = Node(value, None, None)
self.tail = self.head
elif self.length == 1:
# LinkedList has 1 element
self.head = Node(value, self.tail, None)
self.tail._previous = self.head
elif self.length > 1:
# Not empty LinkedList
new_node = Node(value, self.head, None)
self.head._previous = new_node
self.head = new_node
self.length += 1
def pop(self):
removed_node = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head._next._previous = None
self.head = self.head._next
self.length -= 1
return removed_node
def remove(self, value):
if self.length == 1:
self.head = None
self.tail = None
self.length = 0
current_node = self.head
while current_node != None:
if current_node._value == value: # Must remove at least one node
if current_node == self.head: # Case 1: Node is head
self.head = current_node._next
self.head._previous = None
elif current_node == self.tail: # Case 2: Node is tail
self.tail = current_node._previous
self.tail._next = None
elif current_node._value == value: # Case 3: Node is in list but not head or tail
current_node._previous._next = current_node._next
current_node._next._previous = current_node._previous
self.length -= 1
break
current_node = current_node._next
def reverse(self):
self._reverse(self)
def _reverse(self, linked_list): # Recursive reverse
# Base case: 1 element
if linked_list.length == 1:
return linked_list
# Recursive case
reverse_node = linked_list.pop()
linked_list._reverse(linked_list).append(reverse_node._value)
return linked_list
def get_size(self):
return self.length
def is_empty(self):
if self.length == 0:
return True
else:
return False
def __str__(self):
returnString = ""
current_node = self.head
while current_node != None:
returnString = returnString + " " + str(current_node._value)
current_node = current_node._next
return returnString