Linked Lists

Introduction

A Linked List is a linear collection of data elements, called nodes, pointing to the neighbouring node by means of pointer.

Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node or previous node in the sequence.

⚠️ If you wan’t to learn more about linked-lists click here .

Core

The most important part of a linked list is a node. It consist of two things —

1. Data

2. Pointers In Single Linked Lists there is only one pointer (next ) but in Double Linked lists there are two pointers (prev & next ). There can be more than two pointers also. It totally depends on your purpose of creating them.

this while loop is the one on which 75% of linkedLists depends…

Whenever we create an instance of our LinkedList class, the constructor executes and it create a head node with both data and next as null. Then we use its append method to insert items into this list. In this post, we will go through the following methods/operations on Linked Lists —

⚜️ The list

1. Append

2. AppendAt

3. Remove

4. RemoveAt

5. Reverse

6. Swap

7. IsEmpty & Length

8. Traverse

9. Display

10. Search

and a lot more… So, without further ado…

Lets’ begin!!

Initial List

❗️All the code snippets you will see below are just Pseudo code.

🔅 Append

append( item ) {
  let current = this.head;
  let newNode = new Node(item)
  while( current.next !== null ) {
    current = current.next
  }
  current.next = newNode;
  return true;
 }

Append Operation

🔅 AppendAt

appendAt( pos, item ) {
  let counter = 0;
  let current = this.head;
  let newNode = new Node(item);
  while( current.next !== null ) {
    if( counter === pos ){
      newNode.next = current.next
      current.next = newNode
      return true;
    }
    current = current.next
    counter++;
  }
  return false;
 }

AppendAt Operation

🔅 Remove

remove( item ) {
   let current = this.head;
   while( current !== null ) {
     let previous = current;
     current = current.next;
     if( current.data === item ) {
       previous.next = current.next;
       return true;
     }
   }
   return false;
 }

Remove Operation

🔅 RemoveAt

removeAt( pos ) {
  let counter = 0;
  let current = this.head;
  while( current !== null ) {
    let previous = current;
    current = current.next
    if( counter === pos ){
      previous.next = current.next;
      return true;
    }
    counter++;
  }
  return false;
 }

RemoveAt Operation

🔅 Reverse

reverse() {
   let current = this.head.next;
   let prev = null;
   let next;
   while(current !== null) {
     next = current.next
     current.next = prev
     prev = current
     current = next
   }
   this.head.next = prev
   return true
 }

Reverse Operation

It is easy to understand what we see instead of what we read. So, If the mechanism of this reverse function is still unclear to you, I have made a gif in order to show you how the execution goes.

pffff….finally I made it after spending 3 hours in just dragging and dropping.. but hope so it will help you :)

🔅 Swap

swap( nodeOne, nodeTwo ) {
  let current = this.head;
  let counter = 0;
  let firstNode;
  while( current !== null ) {
    current = current.next;
    if( counter == nodeOne ){
      firstNode = current;
    } else if( counter == nodeTwo ) {
      let temp = current.data;
      current.data = firstNode.data;
      firstNode.data = temp;
    }
    counter++;
  }
  return true
 }

Swap Operation

🔅 isEmpty & Length

length() {
  let current = this.head;
  let counter = 0;
  while( current.next !== null ) {
    current = current.next
    counter++;
  }
  return counter;
}isEmpty() {
  return this.length() < 1
}

IsEmpty & Length Operation

🔅 Traverse

If you want to execute a function over each node, then you can use traverse. Just pass the function as shown in the example —

traverse( fn ) {
  let current = this.head;
  while( current.next !== null ) {
    fn(current)
    current = current.next;
  }
  return true;
 }

Traverse Operation

🔅 Display

display() {
  let current = this.head;
  let elements = [];
  while( current !== null ) {
   elements.push( current.data );
   current = current.next
  }
  return elements.join(" ");
}

Display Operation

🔅 Search

search( item ) {
   let current = this.head.next;
   let counter = 0;   while( current ) {
     if( current.data == item ) {
      return counter
     }
     current = current.next
     counter++
   }
   return false;
}

Search Operation

There are still a lot of things that we can do with linked-lists. Never stop doing practice. Explore yourself and think of problems by yourself. The more you think of problems — the more you brain will create links with Data Structures.

Practice

• Hackerrank Data Structures — Linked Lists

• GeekForGeeks Data Structures

• LeetCode Linked Lists