Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
linkedlist python implementation
#!python
class Node(object):
def __init__(self, data):
"""Initialize this node with the given data"""
self.data = data
self.next = None
def __repr__(self):
"""Return a string representation of this node"""
return 'Node({})'.format(repr(self.data))
class LinkedList(object):
def __init__(self, iterable=None):
"""Initialize this linked list and append the given items, if any"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
self.head = None
self.tail = None
self.size = 0
if iterable:
for item in iterable:
self.append(item)
def __repr__(self):
"""Return a string representation of this linked list"""
return 'LinkedList({})'.format(self.as_list())
def items(self):
"""Return a list of all items in this linked list.
Best and worst case running time: Theta(n) for n items in the list
because we always need to loop through all n nodes."""
result = [] # Constant time to create a new list
# Start at the head node
node = self.head # Constant time to assign a variable reference
# Loop until the node is None, which is one node too far past the tail
while node is not None: # Always n iterations because no early exit
# Append this node's data to the results list
result.append(node.data) # Constant time to append to a list
# Skip to the next node
node = node.next # Constant time to reassign a variable
return result # Constant time to return a list
def __getitem__(self, arg):
"""Get the item at the index, or raise KeyError if not an int"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
if type(arg) is not int:
raise TypeError
# If argument is over list size, raise ValueError
if arg >= self.length() or arg < -self.length():
raise IndexError
# Use modulus operator, so index can use negatives
counter = arg % self.length()
currentIndex = 0
if counter == self.length():
return self.last()
current = self.head
while current is not None:
if counter == currentIndex:
return current.data
currentIndex += 1
current = current.next
def as_list(self):
"""Return a list of all items in this linked list"""
items = []
current = self.head
while current is not None:
items.append(current.data)
current = current.next
return items
def get_at_index(self, index):
""" Gets data at an index"""
at_index = self._at_index(index)
if at_index is None:
return None
return at_index.data
def is_empty(self):
"""Return True if this linked list is empty, or False otherwise"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
return self.head is None
def length(self):
"""Return the length of this linked list"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
return self.size
def append(self, item):
"""Insert the given item at the tail of this linked list"""
new_node = Node(item)
# Check if list is empty
if self.head is None:
self.head = new_node
# Otherwise insert after tail node
else:
self.tail.next = new_node
# Update tail node
self.tail = new_node
# Update length
self.size += 1
def prepend(self, item):
"""Insert the given item at the head of this linked list"""
"""Best case Omega(1)"""
"""Worst case O(1)"""
new_node = Node(item)
# Insert before head node
new_node.next = self.head
# Update head node
self.head = new_node
# Check if list was empty
if self.tail is None:
self.tail = new_node
# Update length
self.size += 1
def delete(self, item):
"""Delete the given item from this linked list, or raise ValueError"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
current = self.head
previous = None
found = False
# Find the given item
while not found and current is not None:
if current.data == item:
found = True
else:
previous = current
current = current.next
# Delete if found
if found:
if current is not self.head and current is not self.tail:
previous.next = current.next
current.next = None
if current is self.head:
self.head = current.next
if current is self.tail:
if previous is not None:
previous.next = None
self.tail = previous
# Update length
self.size -= 1
else:
# Otherwise raise an error to tell the user that delete has failed
raise ValueError('Item not found: {}'.format(item))
def size(self):
""" Gets the size of the Linked List
AVERAGE: O(1)
"""
return self.count
def delete_at_index(self, index):
"""Delete the item at the given index from this linked list, or raise ValueError"""
if type(index) is not int:
raise TypeError
# If argument is over list size, raise ValueError
if index >= self.length() or index < -self.length():
raise IndexError
# Use modulus operator, so index can use negatives
counter = index % self.length()
currentIndex = 0
current = self.head
previous = None
found = False
# Find the given item
while not found and current is not None:
if currentIndex == counter:
found = True
else:
previous = current
current = current.next
currentIndex += 1
if found:
if current is not self.head and current is not self.tail:
previous.next = current.next
current.next = None
if current is self.head:
self.head = current.next
if current is self.tail:
if previous is not None:
previous.next = None
self.tail = previous
# Update length
self.size -= 1
else:
raise ValueError('Item not found: {}'.format(item))
def iterable(self):
data = []
current = self.head
while current is not None:
data.append(current.data)
current = current.next
return data
def _find_node(self, data):
current = self.head
while current is not None:
if current.data == data:
return current
current = current.next
def get_at_index(self, index):
"""Return the item at the given index in this linked list, or
raise ValueError if the given index is out of range of the list size.
Best case running time: ??? under what conditions?
Worst case running time: ??? under what conditions? [TODO]"""
if not (0 <= index < self.size):
raise ValueError('List index out of range: {}'.format(index))
counter = self.head
for i in range(index):
counter = counter.next
return counter.data
def insert(self, index, data):
""" Inserts data at a specific index
BEST: O(1)
WORST: O(n)
"""
if index == 0:
self.prepend(data)
return
at_index = self._at_index(index - 1)
if at_index is None:
raise IndexError
if at_index.next is None:
self.append(data)
return
new_node = Node(data)
new_node.next = at_index.next
at_index.next = new_node
def insert_at_index(self, index, item):
"""Insert the given item at the given index in this linked list, or
raise ValueError if the given index is out of range of the list size.
Best case running time: ??? under what conditions? [TODO]
Worst case running time: ??? under what conditions? [TODO]"""
# Check if the given index is out of range and if so raise an error
if not (0 <= index <= self.size):
raise ValueError('List index out of range: {}'.format(index))
if index == 0:
self.prepend(item)
elif index == self.size:
self.append(item)
else:
new_node = Node(item)
node = self.head
previous = None
for i in range(index):
previous = node
node = node.next
previous.next = new_node
new_node.next = node
self.size += 1
def replace(self, old_item, new_item):
"""Replace the given old_item in this linked list with given new_item
using the same node, or raise ValueError if old_item is not found.
Best case running time: ??? under what conditions? [TODO]
Worst case running time: ??? under what conditions? [TODO]"""
if old_item == new_item:
return
node = self.head
while node is not None:
if node.data == old_item:
node.data = new_item
return
node = node.next
raise ValueError('Item not found: {}'.format(old_item))
def find(self, condition):
"""Return an item in this linked list satisfying the given condition"""
"""Best case Omega(1)"""
"""Worst case O(n)"""
current = self.head # Start at the head node
while current is not None:
if condition(current.data):
return current.data
current = current.next # Skip to the next node
return None
def test_linked_list():
ll = LinkedList()
print(ll)
print('Appending items:')
ll.append('A')
print(ll)
ll.append('B')
print(ll)
ll.append('C')
print(ll)
print('head: {}'.format(ll.head))
print('tail: {}'.format(ll.tail))
print('size: {}'.format(ll.size))
print('length: {}'.format(ll.length()))
print('testing: Getting items by index:')
for index in range(ll.size):
item = ll.get_at_index(index)
print('get_at_index({}): {!r}'.format(index, item))
print('Deleting items:')
ll.delete('B')
print(ll)
ll.delete('C')
print(ll)
ll.delete('A')
print(ll)
print('head: {}'.format(ll.head))
print('tail: {}'.format(ll.tail))
print('size: {}'.format(ll.size))
print('length: {}'.format(ll.length()))
print("testing: Linked List replace ___________________")
ll = LinkedList(['A', 'B', 'C'])
ll.replace('A', 'D')
print(ll)
ll = LinkedList(['A', 'B', 'C'])
print(ll)
print("testing: insert_at_index ___________________")
print('size: {}'.format(ll.size))
ll.insert_at_index(0, 'AA')
print(ll)
print("testing: insert_at_index 0, 'AA'___________________")
ll.insert_at_index(2, 'BB')
print("testing: insert_at_index 2, 'BB'___________________")
print(ll)
if __name__ == '__main__':
test_linked_list()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.