24. Linked lists in Python

 

Section 24.1: Single linked list example

This example implements a linked list with many of the same methods as that of the built-in list object.

class Node:

def __init__(selfval): self.data val self.next None

def getData(self): return self.data

def getNext(self): return self.next

def setData(selfval):

self.data val

def setNext(selfval):

self.next val

class LinkedList:

def __init__(self): self.head None

def isEmpty(self):

“””Check if the list is empty””” return self.head is None

def add(selfitem):

“””Add the item to the list””” new_node Node(item) new_node.setNext(self.head) self.head new_node

def size(self):

“””Return the length/size of the list””” count 0

current self.head

while current is not None: count +1

current current.getNext() return count

def search(selfitem):

“””Search for item in list. If found, return True. If not found, return False””” current self.head

found False

while current is not None and not found: if current.getData() is item:

found True else:

current current.getNext()

return found

def remove(selfitem):

“””Remove item from list. If item is not found in list, raise ValueError””” current self.head

previous None found False

while current is not None and not found: if current.getData() is item:

found True else:

previous current

current current.getNext() if found:

if previous is None:

self.head current.getNext() else:

previous.setNext(current.getNext())

else:

raise ValueError

print ‘Value not found.’

def insert(selfpositionitem):

“””

Insert item at position specified. If position specified is out of bounds, raise IndexError

“””

if position self.size() – 1raise IndexError

print “Index out of bounds.” current self.head

previous None pos 0

if position is 0self.add(item)

else:

new_node Node(item) while pos position:

pos +1

previous current

current current.getNext() previous.setNext(new_node) new_node.setNext(current)

def index(selfitem):

“””

Return the index where item is found. If item is not found, return None.

“””

current self.head pos 0

found False

while current is not None and not found: if current.getData() is item:

found True else:

current current.getNext() pos +1

if found: pass

else:

pos None

return pos

def pop(selfposition None):

“””

If no argument is provided, return and remove the item at the head. If position is provided, return and remove the item at that position. If index is out of bounds, raise IndexError

“””

if position self.size(): print ‘Index out of bounds’ raise IndexError

current self.head if position is None:

ret current.getData()

self.head current.getNext() else:

pos previous None while pos position:

previous current

current current.getNext() pos +1

ret current.getData() previous.setNext(current.getNext())

print ret return ret

def append(selfitem):

“””Append item to the end of the list””” current self.head

previous None pos 0

length self.size() while pos length:

previous current

current current.getNext() pos +1

new_node Node(item) if previous is None:

new_node.setNext(current) self.head new_node

else: previous.setNext(new_node)

def printList(self):

“””Print the list””” current self.head while current is not None:

print current.getData() current current.getNext()

Usage functions much like that of the built-in list.

llLinkedList() ll.add(‘l’) ll.add(‘H’) ll.insert(1,‘e’) ll.append(‘l’) ll.append(‘o’) ll.printList()

H e l l o

 

 

 

 

 

*This content is compiled from Stack Overflow Documentation, and the content is written by the beautiful people at Stack Overflow. 

  *This content is compiled from Stack Overflow Documentation, and the content is written by the beautiful people at Stack Overflow.  This work is licensed under cc by-sa.