Lists#
A list is a collection of items where each item holds a relative position with respect to the others. More specifically, we will refer to this type of list as an unordered list. We can consider the list as having a first item, a second item, a third item, and so on. We can also refer to the beginning of the list (the first item or the end of the list (the last item).
Unordered List Abstract Data Type#
The structure of an unordered list, as described above, is a collection of items where each item holds a relative position with respect to the others. Some possible unordered list operations are given below.
UnorderedList()creates a new unordered list that is empty. It needs no parameters and returns an empty list.add(item)adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.remove(item)removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.search(item)searches for the item in the list. It needs the item and returns a boolean value.is_empty()tests to see whether the list is empty. It needs no parameters and returns a boolean value.size()returns the number of items in the list. It needs no parameters and returns an integer.append(item)adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.index(item)returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.insert(pos,item)adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.pop()removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.pop(pos)removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
Implementing an Unordered List#
In order to implement an unordered list, we will construct what is commonly known as a linked list. Recall that we need to be sure that we can maintain the relative positioning of the items. However, there is no requirement that we maintain that positioning in contiguous memory. If we can maintain some explicit information in each item, namely the location of the next item, then the relative position of each item can be expressed by simply following the link from one item to the next.
However location of the first item of the list must be explicitly specified. Once we know where the first item is, the first item can tell us where the second is, and so on. The external reference is often referred to as the head of the list. Similarly, the last item needs to know that there is no next item.
class Node:
def __init__(self, data):
self.data = data
self.next_node = None
def get_data(self):
return self.data
def get_next_node(self):
return self.next_node
def set_data(self, data):
self.data = data
def set_next_node(self, next_node):
self.next_node = next_node
# Todo: Fix methods to have O(1) append
class UnorderedList:
def __init__(self):
self.num_nodes = 0
self.head = None
self.tail = self.head
def is_empty(self):
return self.head == None
def add(self, data):
self.num_nodes += 1
n = Node(data)
if not self.tail:
self.tail = n
n.set_next_node(self.head)
self.head = n
def remove(self, data):
self.num_nodes -= 1
previous = None
current = self.head
while current:
if current.get_data() == data:
if not previous:
self.head = current.get_next_node()
else:
previous.set_next_node(current.get_next_node())
previous = current
current = current.get_next_node()
def search(self, data):
current = self.head
while current:
if current.get_data() == data:
return True
current = current.get_next_node()
return False
def size(self):
return self.num_nodes
def append(self, data):
self.num_nodes += 1
n = Node(data)
if self.tail:
self.tail.set_next_node(n)
else:
self.head = n
def index(self, data):
index = -1
current = self.head
while current:
index += 1
if current.get_data() == data:
return index
current = current.get_next_node()
return index
def insert(self, pos, data):
self.num_nodes += 1
index = -1
n = Node(data)
current = self.head
while current:
index += 1
if index == pos:
n.set_next_node(current.get_next_node())
current.set_next_node(n)
current = current.get_next_node()
def pop(self, pos=-1):
self.num_nodes -= 1
current = self.head
pos = pos if pos >= 0 else self.num_nodes + pos
for i in range(pos):
current = current.get_next_node()
data = current.get_next_node().get_data()
current.set_next_node(None)
return data
def __str__(self):
s = ""
current = self.head
while current != None:
s += f"{current.get_data()} -> "
current = current.get_next_node()
return s.strip(" -> ")
Ordered List Abstract Data Type#
The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending and we assume that list items have a meaningful comparison operation that is already defined. Many of the ordered list operations are the same as those of the unordered list.
OrderedList()creates a new ordered list that is empty. It needs no parameters and returns an empty list.add(item)adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.remove(item)removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.search(item)searches for the item in the list. It needs the item and returns a boolean value.is_empty()tests to see whether the list is empty. It needs no parameters and returns a boolean value.size()returns the number of items in the list. It needs no parameters and returns an integer.index(item)returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.pop()removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.pop(pos)removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
Implementing an Ordered List#
In order to implement the ordered list, we must remember that the relative positions of the items are based on some underlying characteristic. The ordered list of integers given above (17, 26, 31, 54, 77, and 93) can be represented by a linked structure. Again, the node and link structure is ideal for representing the relative positioning of the items.
To implement the OrderedList class, we will use the same technique as seen previously with unordered lists. Once again, an empty list will be denoted by a head reference to None.
# Todo: Fix methods to have O(1) append
class OrderedList:
def __init__(self):
self.num_nodes = 0
self.head = None
self.tail = self.head
def is_empty(self):
return self.head == None
def add(self, data):
self.num_nodes += 1
n = Node(data)
if not self.tail:
self.tail = n
n.set_next_node(self.head)
self.head = n
def remove(self, data):
self.num_nodes -= 1
previous = None
current = self.head
while current:
if current.get_data() == data:
if not previous:
self.head = current.get_next_node()
else:
previous.set_next_node(current.get_next_node())
previous = current
current = current.get_next_node()
def search(self, data):
current = self.head
while current:
if current.get_data() == data:
return True
current = current.get_next_node()
return False
def size(self):
return self.num_nodes
def index(self, data):
index = -1
current = self.head
while current:
index += 1
if current.get_data() == data:
return index
current = current.get_next_node()
return index
def __str__(self):
s = ""
current = self.head
while current != None:
s += f"{current.get_data()} -> "
current = current.get_next_node()
return s.strip(" -> ")
DoublyLinked List Abstract Data Type#
The structure of an DoublyLinked list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item. The ordering is typically either ascending or descending and we assume that list items have a meaningful comparison operation that is already defined. Many of the ordered list operations are the same as those of the unordered list.
DoublyLinkedList()creates a new DoublyLinked list that is empty. It needs no parameters and returns an empty list.add(item)adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.remove(item)removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.search(item)searches for the item in the list. It needs the item and returns a boolean value.is_empty()tests to see whether the list is empty. It needs no parameters and returns a boolean value.size()returns the number of items in the list. It needs no parameters and returns an integer.index(item)returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.pop()removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.pop(pos)removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
Implementing an DoublyLinkedList#
In order to implement the ordered list, we must remember that the relative positions of the items are based on some underlying characteristic. The ordered list of integers given above (17, 26, 31, 54, 77, and 93) can be represented by a linked structure. Again, the node and link structure is ideal for representing the relative positioning of the items.
To implement the OrderedList class, we will use the same technique as seen previously with unordered lists. Once again, an empty list will be denoted by a head reference to None.
# This is an input class. Do not edit.
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
# Feel free to add new properties and methods to the class.
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def setHead(self, node):
node.next
def setTail(self, node):
# Write your code here.
pass
def insertBefore(self, node, nodeToInsert):
# Write your code here.
pass
def insertAfter(self, node, nodeToInsert):
# Write your code here.
pass
def insertAtPosition(self, position, nodeToInsert):
# Write your code here.
pass
def removeNodesWithValue(self, value):
start = self.head
while start:
if start.value == value:
break
start = start.next
next = start.next
previous = start.prev
start.next = start.prev = None
previous.next = next
next.prev = previous
def remove(self, node):
start = self.head
while start:
if start == node:
break
start = start.next
next = start.next
previous = start.prev
start.next = start.prev = None
previous.next = next
next.prev = previous
def containsNodeWithValue(self, value):
node = self.head
while node:
if node.value == value:
return True
node = node.next
return False