Linked Structures

Agenda

  1. Motives
  2. Objectives
  3. Mechanisms
  4. Linked Data Structures

1. Motives

In [3]:
# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
In [2]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from timeit import timeit

def time_array_front_insert_delete(n):
    return timeit('lst.insert(0, None) ; del lst[0]',
                  'lst = list(range({}))'.format(n),
                  number=1000)

ns = np.linspace(100, 10000, 50)
plt.plot(ns, [time_array_front_insert_delete(int(n)) for n in ns], 'ro')
plt.show()
Out[2]:
[<matplotlib.lines.Line2D at 0x8c269e8>]
In [ ]:
# consider:

def concatenate(arr1, arr2):
    """Concatenates the contents of arr1 and arr2 as efficiently (time-wise)
    as possible, so that the resulting structure can be used to index all
    combined elements (arr1's followed by arr2's)."""

    # option 1: O(?)
    for x in arr2:
        arr1.append(x)
    return arr1

    # option 2: O(?)
    arr1.extend(arr2)
    return arr1

    # option 3: O(?)
    return arr1 + arr2

2. Objectives

We would like a new data storage mechanism for constructing data structures that:

  • does not require monolithic, contiguous memory allocation,
  • allows individual elements to be flexibly and efficiently reorganized,
  • and preserves the ability to locate (e.g., via position) and iterate over elements

3. Mechanisms

3.1. Two-Element Lists

In [3]:
# data items
i1 = 'lions'
i2 = 'tigers'
i3 = 'bears'
i4 = 'oh, my'
In [6]:
# creating individual "links"
list1 = [i1,None]
list2 = [i2,None]
list3 = [i3,None]
list4 = [i4,None]
In [7]:
# link-ing them together
list1[1]=list2
list2[1]=list3
list3[1]=list4
In [11]:
# iteration
def link_iter(head):
    while head:
        yield head[0]
        head=head[1]

for i in link_iter(list1):
    print(i)
lions
tigers
bears
oh, my
In [13]:
# prepending

i0 = 'walruses'
list0=[i0,list1]
for i in link_iter(list0):
    print(i)
walruses
lions
tigers
bears
oh, my
In [14]:
# insertion

i2_5 = 'elephants'
list2_5=[i2_5, list3]
list2[1]=list2_5
for i in link_iter(list0):
    print(i)
walruses
lions
tigers
elephants
bears
oh, my
In [15]:
# deletion
list0[1]=list2
list1[1]=None
for i in link_iter(list0):
    print(i)
list1
walruses
tigers
elephants
bears
oh, my
Out[15]:
['lions', None]
In [17]:
list1=None
list1

3.2. "Link" objects

In [18]:
class Link:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
In [19]:
# manually constructing a list
head = Link(i4)
head = Link(i3, head)
head = Link(i2, head)
head = Link(i1, head)
In [20]:
# prepending
def prepend(l, val):
    return Link(val,l)
In [21]:
l = None
for x in range(10):
    l = prepend(l, x)
In [22]:
# iterator
def link_iterator(lst):
    while lst:
        yield lst.val
        lst=lst.next
In [23]:
for x in link_iterator(l):
    print(x)
9
8
7
6
5
4
3
2
1
0
In [24]:
# iterator
#def link_iterator(lst):
#    while lst:
#        yield lst.val
#        lst=lst.next
        
# iteration based on a recursive pattern

def link_iterator_rec(l):
    if l:
        yield l.val
        yield from link_iterator_rec(l.next)
In [25]:
for x in link_iterator_rec(l):
    print(x)
9
8
7
6
5
4
3
2
1
0

4. Linked Data Structures

4.1 Linked List

In [26]:
class LinkedList:
    class Link:
        def __init__(self, val, next=None):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = None
        
    def prepend(self, val):
        temp=Link(val, self.head)
        self.head=temp
    
    def __iter__(self):
        cursor=self.head
        while cursor:
            yield cursor.val
            cursor=cursor.next
            
    def __repr__(self):
        return '[' + ', '.join(str(x) for x in self) + ']'
In [27]:
l = LinkedList()
for x in range(10):
    l.prepend(x)
l
Out[27]:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

4.2 Binary Tree

In [1]:
class BinaryLink:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
In [2]:
# manual construction of a "tree"
root = BinaryLink(10)
root.left = BinaryLink(20)
root.left.left = BinaryLink(15)
root.right = BinaryLink(30)
root.right.right = BinaryLink(45)
In [6]:
def tree_iter(root):
    if root:
        #  pre-order
#        yield root.val
#        yield from tree_iter(root.left)
#        yield from tree_iter(root.right)

# inorder
#        yield from tree_iter(root.left)
#        yield root.val 
#        yield from tree_iter(root.right)
# postorder
        yield from tree_iter(root.left)
        yield from tree_iter(root.right)  
        yield root.val         
# fiddle with order of these yield statements
for i in tree_iter(root):
    print(i)
15
20
45
30
10
In [7]:
# manual construction of a "tree" representing the expression ((5+3)*(8-4))
t = BinaryLink('*')
t.left = BinaryLink('+')
t.left.left  = BinaryLink('5')
t.left.right = BinaryLink('3')
t.right = BinaryLink('-')
t.right.left  = BinaryLink('8')
t.right.right = BinaryLink('4')
In [8]:
def print_expr_tree(t):
    if t:
        if not t.val.isdigit():
            print('(', end='')
        print_expr_tree(t.left)
        print(t.val, end='')
        print_expr_tree(t.right)
        if not t.val.isdigit():
            print(')', end='')
In [9]:
print_expr_tree(t)
((5+3)*(8-4))

4.3 N-ary Tree

In [10]:
class NaryLink:
    def __init__(self, val, n=2):
        self.val = val
        self.children = [None] * n
        
    def __getitem__(self, idx):
        return self.children[idx]
    
    def __setitem__(self, idx, val):
        self.children[idx] = val
        
    def __iter__(self):
        for c in self.children:
            yield c
In [11]:
root = NaryLink('Kingdoms', n=5)

root[0] = NaryLink('Animalia', n=35)
root[1] = NaryLink('Plantae', n=12)
root[2] = NaryLink('Fungi', n=7)
root[3] = NaryLink('Protista', n=5)
root[4] = NaryLink('Monera', n=5)

root[2][0] = NaryLink('Chytridiomycota')
root[2][1] = NaryLink('Blastocladiomycota')
root[2][2] = NaryLink('Glomeromycota')
root[2][3] = NaryLink('Ascomycota')
root[2][4] = NaryLink('Basidiomycota')
root[2][5] = NaryLink('Microsporidia')
root[2][6] = NaryLink('Neocallimastigomycota')

def tree_iter(root):
    if root:
        yield root.val
        for c in root:
            yield from tree_iter(c)
In [12]:
for x in tree_iter(root):
    print(x)
Kingdoms
Animalia
Plantae
Fungi
Chytridiomycota
Blastocladiomycota
Glomeromycota
Ascomycota
Basidiomycota
Microsporidia
Neocallimastigomycota
Protista
Monera