Linked Lists!!! | Learning Data Structures with CompAndCode #2

Updated: Nov 15, 2020

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: