Python Linked Lists: Singly Linked List, Circular Linked List, and Doubly Linked List
闻人望
Python Linked Lists
Node Class
Node class has a constructor that sets the data passed in, and optionally can set the next_node and prev_node.
It also has a str method to give a string representation for printing.
Note that prev_node is only used for Doubly Linked Lists.
class Node:
def __init__ (self, d, n=None, p=None):
self.data = d
self.next_node = n
self.prev_node = p
def __str__ (self):
return ('(' + str(self.data) + ')')
node = Node(3,2,4)
print(node)
print(node.next_node)
print(node.prev_node)
(3)
2
4
LinkedList Class
A LinkedList object has two attributes: a root node that defaults to None, and size that defaults to 0.
Add method receives a piece of data, creates a new Node, setting the root as its next_node, changes the LL’s root pointer to the new node, and increments size.
Find iterates through the nodes until it finds the data passed in. If if finds the data it will return it, otherwise returns None.
Remove needs pointers to this_node and prev_node. If it finds the data, it needs to check if it is in the root node (prev_node is None) before deciding how to bypass the deleted node.
Print_list iterates the list and prints each node.
class LinkedList:
def __init__(self, r = None):
self.root = r
self.size = 0
def add(self, d):
new_node = Node(d, self.root)
self.root = new_node
self.size += 1
def find(self, d):
this_node = self.root
while this_node is not None:
if this_node.data == d:
return d
else:
this_node = this_node.next_node
return None
def remove(self, d):
this_node = self.root
prev_node = None
while this_node is not None:
if this_node.data == d:
if prev_node is not None: # data is in non-root
prev_node.next_node = this_node.next_node
else: # data is in root node
self.root = this_node.next_node
self.size -= 1
return True # data removed
else:
prev_node = this_node
this_node = this_node.next_node
return False # data not found
def print_list(self):
this_node = self.root
while this_node is not None:
print(this_node, end='->')
this_node = this_node.next_node
print('None')
Linked List Test Code
This test code adds nodes to the LinkedList, Prints the list, prints the size, removes an item, and finds an item.
myList = LinkedList()
myList.add(5)
myList.add(8)
myList.add(12)
myList.print_list()
print("size="+str(myList.size))
myList.remove(8)
print("size="+str(myList.size))
print(myList.find(5))
print(myList.root)
(12)->(8)->(5)->None
size=3
size=2
5
(12)
Circular Linked List
Includes attributes root and size.
Includes methods add, find, remove, and print_list.
class CircularLinkedList:
def __init__ (self, r = None):
self.root = r
self.size = 0
def add (self, d):
if self.size == 0:
self.root = Node(d)
self.root.next_node = self.root
else:
new_node = Node (d, self.root.next_node)
self.root.next_node = new_node
self.size += 1
def find (self, d):
this_node = self.root
while True:
if this_node.data == d:
return d
elif this_node.next_node == self.root:
return False
this_node = this_node.next_node
def remove (self, d):
this_node = self.root
prev_node = None
while True:
if this_node.data == d: # found
if prev_node is not None:
prev_node.next_node = this_node.next_node
else:
while this_node.next_node != self.root:
this_node = this_node.next_node
this_node.next_node = self.root.next_node
self.root = self.root.next_node
self.size -= 1
return True # data removed
elif this_node.next_node == self.root:
return False # data not found
prev_node = this_node
this_node = this_node.next_node
def print_list (self):
if self.root is None:
return
this_node = self.root
print (this_node, end='->')
while this_node.next_node != self.root:
this_node = this_node.next_node
print (this_node, end='->')
print()
Circular Linked List Test Code
cll = CircularLinkedList()
for i in [5, 7, 3, 8, 9]:
cll.add(i)
print("size="+str(cll.size))
print(cll.find(8))
print(cll.find(12))
my_node = cll.root
print (my_node, end='->')
for i in range(8):
my_node = my_node.next_node
print (my_node, end='->')
print()
size=5
8
False
(5)->(9)->(8)->(3)->(7)->(5)->(9)->(8)->(3)->
cll.print_list()
cll.remove(8)
print(cll.remove(15))
print("size="+str(cll.size))
cll.remove(5) # delete root node
cll.print_list()
(5)->(9)->(8)->(3)->(7)->
False
size=4
(9)->(3)->(7)->
Doubly Linked List
class DoublyLinkedList:
def __init__ (self, r = None):
self.root = r
self.last = r
self.size = 0
def add (self, d):
if self.size == 0:
self.root = Node(d)
self.last = self.root
else:
new_node = Node(d, self.root)
self.root.prev_node = new_node
self.root = new_node
self.size += 1
def find (self, d):
this_node = self.root
while this_node is not None:
if this_node.data == d:
return d
elif this_node.next_node == None:
return False
else:
this_node = this_node.next_node
def remove (self, d):
this_node = self.root
while this_node is not None:
if this_node.data == d:
if this_node.prev_node is not None:
if this_node.next_node is not None: # delete a middle node
this_node.prev_node.next_node = this_node.next_node
this_node.next_node.prev_node = this_node.prev_node
else: # delete last node
this_node.prev_node.next_node = None
self.last = this_node.prev_node
else: # delete root node
self.root = this_node.next_node
this_node.next_node.prev_node = self.root
self.size -= 1
return True # data removed
else:
this_node = this_node.next_node
return False # data not found
def print_list (self):
if self.root is None:
return
this_node = self.root
print (this_node, end='->')
while this_node.next_node is not None:
this_node = this_node.next_node
print (this_node, end='->')
print()
Doubly Linked List Test Code
dll = DoublyLinkedList()
for i in [5, 9, 3, 8, 9]:
dll.add(i)
print("size="+str(dll.size))
dll.print_list()
dll.remove(8)
print("size="+str(dll.size))
size=5
(9)->(8)->(3)->(9)->(5)->
size=4
print(dll.remove(15))
print(dll.find(15))
dll.add(21)
dll.add(22)
dll.remove(5)
dll.print_list()
print(dll.last.prev_node)
False
False
(22)->(21)->(9)->(3)->(9)->
(3)
类似资料：