Linked Structures

Agenda

1. Motives
2. Objectives
3. Mechanisms

1. Motives

%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()

# 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:
    for x in arr2:
        arr1.append(x)
    return arr1

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

    # option 3:
    return arr1 + arr2

[1, 2, 3] + ['a', 'b', 'c']

[1, 2, 3, 'a', 'b', 'c']

2. Objectives

We need 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

# data items
i1 = 'lions'
i2 = 'tigers'
i3 = 'bears'
i4 = 'oh, my'

i1, i2, i3, i4

('lions', 'tigers', 'bears', 'oh, my')

# creating individual "links"

l1 = [i1, None]
l2 = [i2, None]
l3 = [i3, None]
l4 = [i4, None]

# link-ing them together

l1[0]

'lions'

l1[1] = l2
l2[1] = l3
l3[1] = l4

l = l1

l[0]

'lions'

l[1][0]

'tigers'

l[1][1][0]

'bears'

l[1][1][1][0]

'oh, my'

l

['lions', ['tigers', ['bears', ['oh, my', None]]]]

# iteration

link = l
while link:
    print(link[0])
    link = link[1]
    

lions
tigers
bears
oh, my

# prepending

l0 =['goats', None]

l0[1] = l1

l = l0

link = l
while link:
    print(link[0])
    link = link[1]

goats
lions
tigers
bears
oh, my

# insertion

#between tiger and lion

newlink =['elephant', None]

newlink = ['elephant', l[1][1]]
l[1][1] = newlink

link = l
while link:
    print(link[0])
    link = link[1]

goats
lions
elephant
tigers
bears
oh, my

3.2. "Link" objects

class Link:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

# manually constructing a list

l1 = Link(i1)
l2 = Link(i2)
l3 = Link(i3)
l4 = Link(i4)

l1.next = l2
l2.next = l3
l3.next = l4

l = l1

l.val

'lions'

l.next.val

'tigers'

l.next.next.val

'bears'

head = Link(i4)

#prepend an element

head = Link(i3, next=head) #next= optional, head = Link(i3, head)

head = Link(i2, next=head)

head = Link(i1, next=head)

head.val

'lions'

head.next.val

'tigers'

# iteration

link = head

while link:
    print(link.val)
    link = link.next
    

lions
tigers
bears
oh, my

# prepend an element

head = Link('goat', next = head)

# iteration based on a recursive pattern

class LinkedList:
    def __init__(self):
        self.head = None
        
    def prepend(self, val):
        self.head = Link(val, next=self.head)
        
    def __iter__(self):
        cursor = self.head
        while cursor:
            yield cursor.val
            cursor = cursor.next
            
    def __getitem__(self, idx):
        cursor = self.head
        for _ in range(idx):
            cursor = cursor.next
        return cursor.val
    
    def __repr__(self):
        return '[' + ', '.join(str(x) for x in self) + ']'

l = LinkedList()

l.prepend(0)

l

[0]

for x in range(1,10):
    l.prepend(x)

l

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

l[2] #not working 

7

class LinkedList:
    def __init__(self):
        self.head = None
        
    def prepend(self, val):
        self.head = Link(val, next=self.head)
        
    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) + ']'
    
    def __getitem__(self, idx):
        cursor = self.head
        for _ in range(idx):
            cursor = cursor.next
        return cursor.val

l = LinkedList()

for x in range(0,10):
    l.prepend(x)

l

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

l[3]

6

class BinaryLink:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# manual construction of a "tree"

t = BinaryLink('hello', left = BinaryLink('world'), right = BinaryLink('universe'))

t.val

'hello'

t.right.val

'universe'

t.left.val

'world'

def tree_iter(root):
    if root:
        yield root.val
        yield from tree_iter(root.left) #self-reading: yield from
        yield from tree_iter(root.right)

for x in tree_iter(t):
    print(x)

hello
world
universe

#self-studying

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

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)

for x in tree_iter(root):
    print(x)

Kingdoms
Animalia
Plantae
Fungi
Chytridiomycota
Blastocladiomycota
Glomeromycota
Ascomycota
Basidiomycota
Microsporidia
Neocallimastigomycota
Protista
Monera