Introduction
Linked lists are a basic data structure used in programming.
Linked List (Wikipedia)
Do not uses any existing Python modules "that do" linked lists. The purpose of these
projects is to "do them" yourself.
Project #1
Create an interactive program that
- ask the user to input data items
- maintain separate linked lists for integers, floats, and strings
- maintain the lists in sort order
- allow the user to
- list all of the items in the lists
- test if a given item is in the lists
- delete items from the lists
- empty a list (delete all items in a list)
Project #2
Linked lists are linear (one dimensional) data structures.
Create a linked list of linked lists to allow two dimensions.
For example a set of X,Y coordinates that represent the
location of islands in a vast empty ocean.
The ocean is mostly empty so using a two dimension array
could be a waste of space. (Use integers to simplify things.)
Remember coordinates are ordered (1,2,3,4,...) not random (3,2,4,1,...).
Create a linked list of X coordinates containing a linked lists of Y coordinates.
Create an interactive program that
- ask the user to enter X,Y coordinates of an island
- store the island's coordinates
- allow the user to
- list all of the islands
- list all of the islands given an X coordinate
- test if there is an island at coordinates X,Y
- delete individual islands (if they exist)
- empty all lists (delete all islands)
Project #3
Duplicate project #2 except for 3 dimensions.
Singly Linked List
Doubly Linked List
Code Example - Can you complete this code?
#!/usr/bin/python3
# ===================================================================
# demonstrate doubly linked list
# ===================================================================
#
# (list head) (list node) (list node) (list node)
# +-------+ +-------+ +-------+ +-------+
# | first |---->| flink |---->| flink |---->| None |<--+
# +-------+ +-------+ +-------+ +-------+ |
# | last |--+ | None |<----| blink |<----| blink | |
# +-------+ | +-------+ +-------+ +-------+ |
# | |
# +------------------------------------------+
#
# flink - forward link (sometimes call next link).
# blink - backward link (sometimes called previous link).
# first - link to first element in the list.
# last - link to last element in the list.
#
# ===================================================================
# -------------------------------------------------------------------
# ----- define list node (element) class
# -------------------------------------------------------------------
class Node:
def __init__(self,data):
self.data = data
self.flink = None
self.blink = None
return
.... add class methods (suggestions)
get data
set data
get flink
get blink
set flink
set blink
set flink and blink (one method, two actions)
# -------------------------------------------------------------------
# ---- define list head class
# -------------------------------------------------------------------
class LinkedList:
def __init__(self):
self.first = None
self.last = None
return
.... add class methods (suggestions)
add at head of list
add at tail of list
add after a node
add before a node
delete node
test if empty
get the number of nodes in a list
locate a node
get first node
get last node
clear list
# -------------------------------------------------------------------
# ---- main (for testing)
# -------------------------------------------------------------------
if __name__ == '__main__':
def print_list_forward(linked_list):
....
return
def print_list_backward(linked_list):
....
return
def print_node(node):
....
return
def print_list_head(linked_list):
...
return
def print_list_tail(linked_list):
...
return
# --- create linked list and insert values
ll1 = LinkedList()
values = [31,77,17,93,26,54]
.... insert values at end of list
.... print the size of the list
.... print list (forwards and backwards)
.... insert 120 before 17
.... insert 800 after 77
.... print list
# --- insert nodes at the end of a list
ll2 = LinkedList()
values = [193,131,177,117,193,126,154]
.... insert values into the list (maintain sort order)
.... insert 120
.... insert 125
.... print list
# --- test removing nodes
.... remove 177 from list ll2
.... remove 180 from list ll2
# --- locate value in the list?
.... locate 154 in list ll2
.... locate 155 in list ll2
If you would like to see linked list C code click
Here
.