Introduction:
In this post I'm going to be talking about the 'Linked List' Data Structure which is a follow on from the last 'Learning Data Structures with CompAndCode' post (https://www.thenibblebyte.com/post/lets-learn-lists-learning-data-structures-with-compandcode ). Be sure to check that out before reading this post.
Theory:
Linked Lists are an example of a dynamic Data Structure that hold an ordered sequence.
The term node is used, rather than element.
Each element isn't necessarily held in consecutive memory locations.
Each node has a Data Field and a Pointer/Link Field.
Data Field - Holds the actual information, e.g. a string or number.
Pointer Field - Contains the address of the next node in the sequence.
The Link Field in the last element is null.
When initialised, there's a Pointer Variable containing the address of the first element in the list.
Defining a Node Record:
type nodeType
string name //Data Field, cast as a string.
integer pointer //Pointer Field, cast as an integer.
endType
dim Names [0..3] of nodeType //Creates a list of 5 nodes.
Initialising a Linked List:
Requires 2 lists.
1 for the actual data.
1 for the free spaces.
When a new node is added; it is put in the the node, pointed to by nextFree.
When a node is removed; it's position is linked into the free space list.
Pointer Variables:
start - Points to the first item in the list.
nextFree - Pointer to the next free location.
E.g.:
We have a Linked List of different countries and we want to organise them alphabetically.
Initialising an empty list:
To clarify, Start = NULL because there are no nodes in the list. If there was 1 element then it would be at index position 1.
nextFree is 0 because that's where the next node will be added to.
Adding in the Data:
start changes to 0 because that's where the first element is.
nextFree changes to 3 because of the addition of the elements.
The pointers maintain the sequence of alphabetical order.
Inserting an Item:
When inserting a new node, it will need to go between 2 nodes, therefore changing the pointer values.
The node behind will point to the new node.
The node in front will then point to either the next node or nextFree (which needs to be updated!).
Steps:
Store the new node in the index position of nextFree.
Change the value of nextFree.
Change the value of any nodes affected.
The example below show's Columbia being added which means the pointers have to change.
Pseudocode:
Names[p].name //Holds the name in node[p].
Names[p].pointer //Holds the value of the pointer in node[p].
Deleting and Item:
Essentially this is done by changing the pointers so that the designated node is no longer included in the Linked List.
Steps
Follow the pointers to find the designated node.
Change the pointers to no longer include the designated node.
Change nextFree if required.
Python & Java Implementation:
The reason why I didn't implement these myself is because they are quite complex and that the solutions out there are more efficient. With that being said, when I was doing A Level Computer Science, we didn't have to memorise the Linked List Algorithm. This means that as long as you know the theory then you should be fine. Also remember that in the exams, pseudocode is usually an acceptable format, as a response, in exam questions so the syntax isn't too significant.
Final Things:
If you have any topics that you want me to blog about then please let me know in the comments!!!
I aim to keep this series at 1 post per month! Make sure you like, comment, share this blog post.
Follow CompAndCode on all platforms! Thank You TheNibbleByte!! Hashtags: #computerscience #coding #programming #technology #python #programmer #computer #tech #developer #coder #java #javascript #code #codinglife #webdeveloper #softwareengineer #engineering #machinelearning #softwaredeveloper #html #programmers #software #artificialintelligence #computerengineering #linux #datascience #cybersecurity #programmingmemes #hacking #bhfyp #informationtechnology #programminglife #hacker #css #pythonprogramming #php #webdesign #ai #science #programmerlife #codingmemes #deeplearning #developers #programmerhumor #coderlife #codingisfun #computers #kalilinux #developerlife #development #ethicalhacking #softwareengineering #computerprogramming #windows #coders #codingbootcamp #security #geek #daysofcode #programmingisfun #compandcode
code
coder
coding
codinglife
compandcode
computer
computerscience
developer
html
java
javascript
machinelearning
programmer
programming
python
softwaredeveloper
softwareengineer
webdeveloper
tech
technology
Comments