Algorithms

问题
　　
    

Python programming

# Implementing pointers and objects
class linked_list():
    def __init__(self, size):
        self.next = ['NIL', 3, 'NIL', 8, 2, 1, 5, 6]   
        self.key = [0, 4, 1, 0, 16, 0, 9, 0]
        self.prev = [0, 5, 2, 0, 7, 0, 'NIL', 0]
        self.free = self.free_id()

    def nextm(self, x):
        cur = self.key.index(x)
        return self.next[cur]

    def prevm(self, x):
        cur = self.key.index(x)
        return self.prev[cur]

    def free_id(self):
        try:
            return self.key.index(0)
        except ValueError:
            return 'NIL'


def allocate_object(L):
    cur = L.free
    if  cur == 'NIL':
        return 'Error. Out of space.'
    else:

        L.key[cur] = 'allocated'
        L.free = L.free_id()
        return cur

def free_object(L, i):
    L.key[i-1] = 0
    L.free = L.free_id()


# next = ['NIL', 3, 'NIL', 8, 2, 1, 5, 6]
# key = [0, 4, 1, 0, 16, 0, 9, 0]
# prev = [0, 5, 2, 0, 7, 0, 'NIL', 0]

if __name__ == '__main__':
    print('Build a linked list object with the size of 8')
    ll = linked_list(8)
    # next = ['NIL', 3, 'NIL', 8, 2, 1, 5, 6]
    # key = [0, 4, 1, 0, 16, 0, 9, 0]
    # prev = [0, 5, 2, 0, 7, 0, 'NIL', 0]
    print(ll.next, ll.key, ll.prev, ll.free)
    print('allocating the cursor')
    print(allocate_object(ll))
    print(ll.next, ll.key, ll.prev, ll.free)

    print('free the position of 3')
    free_object(ll, 3)

    print(ll.next, ll.key, ll.prev, ll.free)
    print('the next and previous key of element 16')
    print(ll.nextm(16), ll.prevm(16))
    print("the next and previous key of element 'allocated'")
    print(ll.nextm('allocated'), ll.prevm('allocated'))

结果打印:
Build a linked list object with the size of 8
['NIL', 3, 'NIL', 8, 2, 1, 5, 6] [0, 4, 1, 0, 16, 0, 9, 0] [0, 5, 2, 0, 7, 0, 'NIL', 0] 0
allocating the cursor
0
['NIL', 3, 'NIL', 8, 2, 1, 5, 6] ['allocated', 4, 1, 0, 16, 0, 9, 0] [0, 5, 2, 0, 7, 0, 'NIL', 0] 3
free the position of 3
['NIL', 3, 'NIL', 8, 2, 1, 5, 6] ['allocated', 4, 0, 0, 16, 0, 9, 0] [0, 5, 2, 0, 7, 0, 'NIL', 0] 2
the next and previous key of element 16
2 7
the next and previous key of element 'allocated'
NIL 0

Reference,

    1. Introduction to algorithms