10 Linked List ADT

The inefficiencies of lists occur because the references stored are contiguous.


class _Node: 
	""" this is an item in a linked list and is a
	private class utilized by the LinkedList class, 
	not the client code

	== Attributes == 
	item: data stored in this node
	next: the next node in the list or None
	""" 
	item: Any 
	next: Optional[_Node]

	def __init__(self, item: Any) -> None:
		"""Initialize a new node storing <item>, with 
		no next node>
		"""
		self.item = item 
		self.next = None

class LinkedList:
	""" A linked list implementation of the List ADT.
	=== Private Attributes ===
	"""
	_first: Optional[_Node]
	def __init__(self) -> None:
		"""
		blah blah blah
		"""
		self._first = None

_Node:

LinkedList

Never lose the pointer to the next node before reassigning

![](/img/user/Introduction to CS/attachments/Pasted image 20250219175919.webp)
![](/img/user/Introduction to CS/attachments/Pasted image 20250219180103.webp)

Traversing Linked Lists

def print_items(self) -> None:
	curr = self.first
	while curr is not None: 
		print(curr.item)
		curr.next

Linked List Append

def append(self, item: Any) -> None:	
	curr = self._first
	if curr is None: 
		self._first = _Node(item)
	while curr is not None: 
		if curr.next is None: 
			curr.next = _Node(item)
		curr = curr.next

def append(self, item: Any) -> None: 
	curr = self._first 
	if curr == None: 
		self._first(_Node(item))
	else: 
		while curr.next is not None: 
			curr = curr.next
		curr.next = new_node

Initializer Idea

class LinkedList: 
	def __init__(self, items: list) -> None:
		if not items:
			curr = self.first = _Node(items[0])
			for i, item in enumerate(items):
				if i > 0: 
					curr._next = _Node(item)
					curr = curr._next

Insert Idea

class LinkedList: 
	def insert(self, index: int, item: Any) -> None:
		if index == 0: 
			new_node = _Node(item)
			self.first, new_node.next = new_node, self._first
		else:
			curr = self._first
			curr_index = 0 
	
			while curr is not None and curr_index < index -1:
				curr = curr.next
				curr_index += 1 
				
			if curr is None: 
				raise IndexError 
			else: 
				new_node = _Node(item)
				curr.next, new_node.ext = new_node, curr.next

Delete Idea

	def pop(self, index: int) -> Any: 
		curr = self._first 
		curr_index = 0 
		
		if index == 0 and curr is not None:
			self._first = curr.next
			return curr.item
		
		while curr is not None and current_index < index - 1: 
			curr = curr.next
			curr_index += 1
		
		if curr is None or curr.next is None: 
			raise IndexError 
		
		else: 
			replacement = curr.next.next
			value = curr.next.item
			curr.next = replacement
			return value

Runtime vs Array-based lists

Look up by index i: