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
