Demonstrate Linked Lists

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

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

Project #3

Duplicate project #2 except for 3 dimensions.

Singly Linked List

image missing

Doubly Linked List

image missing

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 .