DataStructures Series #7 – The List ADT

Originally posted on my medium page: https://medium.com/@otarutunde

The List ADT

A list is a linear collection of data elements, unlike the array ADT, its order is not given by their physical placement in memory. Instead each element points to the next.

The list is mostly implemented using a collection of nodes which together forms a sequence (known as linkedlist). In its most basic form, each node contains two cells, one cell for the data and the other cell contains the memory address of the next node.

The LinkedList ADT
photo credit: rubyguides.com

List Operations:

  • Insert (data, position)
  • Delete (data)
  • Get (data)
  • Insert (data)

Insert (data, position) — This will insert a node having the data at the specified position in the list

Delete (data) — This will delete the last node having the data in the list

Get (data) — This fetches the node having the data from the list sequence

Insert (data)— This will add a new node having the data to the end of the list

Implementation

The approach here is to create a class representing a node with its following properties.

Below is a pseudocode implementation for creating a list of 1 –> 3 –> 4:

Class Node {

  int data = null;
  Node nextNode = null;

  class_constructor(data, nextNode) {
     this.data = data;
     this.nextNode = nextNode;
  }

}

Node four = new Node(4, null);
Node three = new Node(3, four);
Node one = new Node(1, three);

Insert a Node with data value 2 at position 1 (zero indexed) so the new sequence becomes 1 –> 2 –> 3 –> 4:

Insert (2, 1)

Node currentNode = one;
Node previousNode = null;
listCurrentPosition = 0;
while (currentNode is not null) {
   if (listCurrentPosition == 1) {
       Node dataNode = new Node(2, currentNode);
       previousNode.nextNode = dataNode;
       break out of current loop;
   }   
   previousNode = currentNode;
   currentNode = currentNode.nextNode;
   listCurrentPosition++;
}

Delete node with data 3 in the list so the sequence becomes: 1 –> 2 –> 4:

Delete (3)

Node currentNode = one;
Node previousNode = null;
while (currentNode.nextNode is not null) {
   if (currentNode.data == 3) {
      previousNode.nextNode = currentNode.nextNode;
      break out of the while loop;
   }
   previousNode = currentNode;
   currentNode = currentNode.nextNode;
}

Get node having data 2:

Get (2)

Node currentNode = one;
while (currentNode.nextNode is not null) {
   if (currentNode.data == 2) {
      return currentNode;
   }
   currentNode = currentNode.next;
}

Insert node having data 5 into the list so the sequence becomes 1 –> 2 –> 4–> 5:

Insert (5)

Node currentNode = four;
Node five = new Node(5, null);
four.nextNode = five;

Real life Applications

  • A one way music playlist— Music playlists with only the forward button.

REFERENCES:

One thought on “DataStructures Series #7 – The List ADT”

Comments are closed.