ComputerScienceALevels/LinkedListComplete.py at master · sirfaheem/ComputerScienceALevels · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
LIST_SIZE = 8
NULL = -1
freeListPtr = 0
startPointer = NULL

class Node:
        data = '' #STRING
        nextP = NULL #INTEGER
thisList = [Node()]


def init():
    global startPointer
    global freeListPtr
    global thisList
    for x in range (LIST_SIZE):
        thisList.append(Node())

    for x in range(LIST_SIZE):
        thisList[x].nextP = x + 1
    thisList[LIST_SIZE-1].nextP = NULL
    freeListPtr = 0 #FreeList points to the first element of the array
    startPointer = NULL #StartPtr is NULL because list is empty.


def insert(s):
    global startPointer
    global freeListPtr
    global thisList
    if freeListPtr != NULL: #List has space for data
        newNodePtr = freeListPtr
        thisList[newNodePtr].data = s
        freeListPtr = thisList[freeListPtr].nextP
        # Find insertion point
        if startPointer == NULL:  # List is empty
            thisList[newNodePtr].nextP = NULL
            startPointer = newNodePtr #becomes 1st element
        else:
            prevPtr = NULL
            thisPtr = startPointer
            while thisPtr != NULL and thisList[thisPtr].data < s:
                prevPtr = thisPtr
                thisPtr = thisList[thisPtr].nextP

            if prevPtr == NULL:  # Insert at start of list
                thisList[newNodePtr].nextP = startPointer
                startPointer = newNodePtr
            else:  # Insert in middle or end of list
                thisList[newNodePtr].nextP = thisList[prevPtr].nextP
                thisList[prevPtr].nextP = newNodePtr
    else:
        print('the list is full')

def outputAllNodes():
    global startPointer
    global thisList
    nodePtr = startPointer
    while nodePtr != NULL:
        print(f"{thisList[nodePtr].data} -> ", end="")
        nodePtr = thisList[nodePtr].nextP
    print("None")

def delete(s):
    global startPointer
    global freeListPtr
    global thisList
    if startPointer == NULL:  # List is empty
        print("List is empty, cannot delete node.")
    else:
        prevPtr = NULL
        thisPtr = startPointer
        while thisPtr != NULL and thisList[thisPtr].data != s:
            prevPtr = thisPtr
            thisPtr = thisList[thisPtr].nextP

        if thisPtr == NULL:  # Data not found
            print(f"Data '{s}' not found in list.")
        else:
            if prevPtr == NULL:  # Data found at start of list
                startPointer = thisList[thisPtr].nextP
            else:  # Data found in middle or end of list
                thisList[prevPtr].nextP = thisList[thisPtr].nextP
            # Add deleted node to free list
            thisList[thisPtr].data = ''
            thisList[thisPtr].nextP = freeListPtr
            freeListPtr = thisPtr

def search(s):
    global startPointer
    global thisList
    thisPtr = startPointer
    index = NULL
    while thisPtr != NULL:
        index += 1
        if thisList[thisPtr].data == s:
            return index
        thisPtr = thisList[thisPtr].nextP
    return NULL

def dump():
    global startPointer
    global freeListPtr
    global thisList
    print('startPtr: ', startPointer)
    print('freelist: ', freeListPtr)
    for x in range(LIST_SIZE):
        print(x, end=' ')
        print(thisList[x].data, end=' ')
        print(thisList[x].nextP)


init()
dump()
insert('muntazir')
insert('amr')
insert('hamdan')
insert('abbad')
insert('ibad')
insert('hamza')
insert('ibraheem')
insert('faheem')
#insert('ali')
print()
dump()
print()
outputAllNodes()
print('found at : ', search('faheem'))
print('found at : ', search('srihari'))
#insert('asim')
#outputAllNodes()
##delete('qazi')
##delete('abbad')
##dump()
##insert("hadi")
##outputAllNodes()
##print('found at : ', search('qazi'))