May 23, 2021
Code Baselined: May 19, 2021
Synopsis
This paper presents Python code that implements a LIFO stack using a singly linked list without using built-in Python methods.
Introduction
Python, along with C++, is one of the programming languages covered in the Penetration Testing Student Online Learning Path offered by INE. According to INE, competent penetration testers need to be proficient with shell scripting and at least one modern programming language.
I find it much more difficult to learn a new programming language while at the same time trying to learn how to apply the programming language to a new application, namely cybersecurity exploit development. Based on my experience so far, the INE Python training modules present the basics of the language in a very simple, straightforward way, but then the lab exercises dive right into advanced concepts leaving the learner to struggle. The approach I’ve adopted now is to postpone taking the lab exercises until becoming more comfortable with the nuances of the Python language.
So, to achieve the aforementioned goal, I chose to implement a LIFO (Last In, First Out) stack as a singly linked list similar to the data structure I implemented previously in a C# project.
Python 3.9.5 64-bit was used for this programming exercise and can be downloaded here. The code editor used was Visual Studio Code 1.56.2 for Windows and can be downloaded here. It’s interesting to note that Visual Studio Code out of the box is only a code editor not a fully featured IDE. In order to execute Python code or code in any other language directly from the editor, the language compiler needs to be downloaded and installed manually. Once the desired language support is installed from the Customize, Tools and languages section in Visual Studio Code, then code execution can be performed from within the editor as in Microsoft Visual Studio.
Design
For this exercise, I wrote all the code to manage the linked list without using built-in Python methods. I chose a singly linked list data structure to implement a stack. In a stack, the last data item pushed or added to the stack is the first data item popped or removed (LIFO) from the stack.
The length of the list, i.e., depth of the stack, is finite. While the list length is predetermined in the code, a message indicating the list length is displayed to the user upon program execution.
Additional information on linked list structure and processing can be found in my earlier C# linked list write-up.
The data structure I used to implement the linked list in Python is a List of Lists. The lists are the nodes that represent the Info/Link data fields that can be referenced as any other list item. For example, LinkedList[0][0] references the Info data component of the first node. Likewise, LinkedList[0][1] references the Link data component of that first node.
As expected, functions were created to handle the fundamental list processing actions: Insert, Delete, and View. The Insert function accepts a parameter for the data item accepted from the user, while the other two functions do not accept parameters.
In order to mimic a Switch statement or branch table in Python, a Dictionary structure was implemented.
Code
# Linked List coding exercise in Python 3.9.5
# List is managed without using built-in Python methods.
#
# Author: Gerard Sczepura
# Date: May 21, 2021
#from typing import List
LinkedList = [['', 1], ['', 2], ['', 3], ['', 4], ['', -1]]
ListSize = len(LinkedList)
pToS = -1
pAvail = 0
Info = 0
Link = 1
def Insert(ItemVal):
"""Pushes a new value on the List"""
global LinkedList, pToS, pAvail
global Info, Link
pSave = pToS
if pAvail == -1:
print('List is Full!')
else:
pToS = pAvail
pAvail = LinkedList[pAvail][Link]
LinkedList[pToS][Info] = ItemVal
LinkedList[pToS][Link] = pSave
print('Data Item: ' + "'" + ItemVal + "'" + ' Pushed')
return
def Delete():
"""Pops the top value from the List"""
global LinkedList, pToS, pAvail
global Info, Link
if pToS == -1:
print('List is Empty!')
else:
pSave = pAvail
pAvail = pToS
pToS = LinkedList[pToS][Link]
LinkedList[pAvail][Link] = pSave
print('Data Item: ' + "'" + LinkedList[pAvail][Info] + "'" + ' Popped')
LinkedList[pAvail][Info] = ''
return
def View():
"""Displays the contents of the List"""
global LinkedList, pToS
global Info, Link
if pToS != -1:
pNext = pToS
while pNext != -1:
print(LinkedList[pNext][Info])
pNext = LinkedList[pNext][Link]
else:
print('List is Empty!')
return
function_switch = {
1: Insert,
2: Delete,
3: View
}
print('*** Linked List Processing Program ***')
print(' ~~~ Function Insert',Insert.__doc__)
print(' ~~~ Function Delete',Delete.__doc__)
print(' ~~~ Function View',View.__doc__)
print()
print('Maximum List Length is: ' + str(ListSize))
UserIn = 0
while UserIn != 9:
print()
UserIn = int(input("""Select an Action:
1: Insert
2: Delete
3: View
9: Exit
"""))
if UserIn in function_switch:
if UserIn == 1:
UsrData = input('Enter list item: ')
function_switch[UserIn] (UsrData)
else:
function_switch[UserIn] ()
else:
if UserIn == 9:
break
else:
print('Invalid Entry!')
print(LinkedList) #Display the list structure for debugging
Test Plan
6 NOP – invalid entry
3 View – empty list
1 Add – “First”
1 Add – “Second”
3 View – data items displayed
1 Add – “Third”
2 Delete – Pop item from top of list (LIFO)
1 Add – “Third”
1 Add – “Fourth”
1 Add – “Fifth”
3 View – full list displayed
1 Add – “Sixth” list full
2 Delete – Pop list
2 Delete – Pop list
2 Delete – Pop list
2 Delete – Pop list
2 Delete – Pop list
2 Delete – Pop list, empty list
9 Exit
Execution Trace Log
*** Linked List Processing Program ***
~~~ Function Insert Pushes a new value on the List
~~~ Function Delete Pops the top value from the List
~~~ Function View Displays the contents of the List
Maximum List Length is: 5
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
6
Invalid Entry!!
[['', 1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
3
List is Empty!
[['', 1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: First
Data Item: 'First' Pushed
[['First', -1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Second
Data Item: 'Second' Pushed
[['First', -1], ['Second', 0], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
3
Second
First
[['First', -1], ['Second', 0], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Third
Data Item: 'Third' Pushed
[['First', -1], ['Second', 0], ['Third', 1], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'Third' Popped
[['First', -1], ['Second', 0], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Third
Data Item: 'Third' Pushed
[['First', -1], ['Second', 0], ['Third', 1], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Fourth
Data Item: 'Fourth' Pushed
[['First', -1], ['Second', 0], ['Third', 1], ['Fourth', 2], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Fifth
Data Item: 'Fifth' Pushed
[['First', -1], ['Second', 0], ['Third', 1], ['Fourth', 2], ['Fifth', 3]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
3
Fifth
Fourth
Third
Second
First
[['First', -1], ['Second', 0], ['Third', 1], ['Fourth', 2], ['Fifth', 3]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
1
Enter list item: Sixth
List is Full!
[['First', -1], ['Second', 0], ['Third', 1], ['Fourth', 2], ['Fifth', 3]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'Fifth' Popped
[['First', -1], ['Second', 0], ['Third', 1], ['Fourth', 2], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'Fourth' Popped
[['First', -1], ['Second', 0], ['Third', 1], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'Third' Popped
[['First', -1], ['Second', 0], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'Second' Popped
[['First', -1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
Data Item: 'First' Popped
[['', 1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
2
List is Empty!
[['', 1], ['', 2], ['', 3], ['', 4], ['', -1]]
Select an Action:
1: Insert
2: Delete
3: View
9: Exit
9
Copyright secured by Digiprove © 2021 Gerard Sczepura