Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Saturday, June 6

    Design Linked List

    C/C++ No Comments8 Mins ReadakshayBy

    Problem Statement:

    Design and implement a custom singly linked list class with the following operations:

    Operations:

    • get(index): Return the value of the node at the specified index (0-indexed). If index is invalid, return -1.
    • addAtHead(val): Insert a node at the beginning of the list.
    • addAtTail(val): Append a node at the end of the list.
    • addAtIndex(index, val): Insert a node before the index-th node in the list.
    • deleteAtIndex(index): Delete the node at the given index.

    Approach:

    • Use a custom Node class that holds val and next attributes.
    • Maintain a head pointer to the first node and a size to track the list length.
    • Each operation ensures index bounds are checked.
    • Traverse the list up to the required index using a loop.
    • All operations are implemented with time complexity O(n) in the worst case.
    
function Node(val) {
  this.val = val;
  this.next = null;
}

var MyLinkedList = function () {
  this.head = null;
  this.size = 0;
};

MyLinkedList.prototype.get = function (index) {
  if (index < 0 || index >= this.size) return -1;
  let curr = this.head;
  for (let i = 0; i < index; i++) curr = curr.next;
  return curr.val;
};

MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = new Node(val);
  newNode.next = this.head;
  this.head = newNode;
  this.size++;
};

MyLinkedList.prototype.addAtTail = function (val) {
  const newNode = new Node(val);
  if (!this.head) this.head = newNode;
  else {
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = newNode;
  }
  this.size++;
};

MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index < 0 || index > this.size) return;
  if (index === 0) return this.addAtHead(val);
  if (index === this.size) return this.addAtTail(val);
  const newNode = new Node(val);
  let curr = this.head;
  for (let i = 0; i < index - 1; i++) curr = curr.next;
  newNode.next = curr.next;
  curr.next = newNode;
  this.size++;
};

MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || index >= this.size) return;
  if (index === 0) this.head = this.head.next;
  else {
    let curr = this.head;
    for (let i = 0; i < index - 1; i++) curr = curr.next;
    curr.next = curr.next.next;
  }
  this.size--;
};
    
    typedef struct Node {
      int val;
      struct Node* next;
  } Node;
  
  typedef struct {
      Node* head;
      int size;
  } MyLinkedList;
  
  MyLinkedList* myLinkedListCreate() {
      MyLinkedList* obj = (MyLinkedList*)malloc(sizeof(MyLinkedList));
      obj->head = NULL;
      obj->size = 0;
      return obj;
  }
  
  int myLinkedListGet(MyLinkedList* obj, int index) {
      if (index < 0 || index >= obj->size) return -1;
      Node* curr = obj->head;
      for (int i = 0; i < index; i++) curr = curr->next;
      return curr->val;
  }
  
  void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
      Node* node = (Node*)malloc(sizeof(Node));
      node->val = val;
      node->next = obj->head;
      obj->head = node;
      obj->size++;
  }
  
  void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
      Node* node = (Node*)malloc(sizeof(Node));
      node->val = val;
      node->next = NULL;
      if (!obj->head) obj->head = node;
      else {
          Node* curr = obj->head;
          while (curr->next) curr = curr->next;
          curr->next = node;
      }
      obj->size++;
  }
  
  void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
      if (index < 0 || index > obj->size) return;
      if (index == 0) {
          myLinkedListAddAtHead(obj, val);
          return;
      }
      Node* node = (Node*)malloc(sizeof(Node));
      node->val = val;
      Node* curr = obj->head;
      for (int i = 0; i < index - 1; i++) curr = curr->next;
      node->next = curr->next;
      curr->next = node;
      obj->size++;
  }
  
  void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
      if (index < 0 || index >= obj->size) return;
      Node* temp;
      if (index == 0) {
          temp = obj->head;
          obj->head = obj->head->next;
      } else {
          Node* curr = obj->head;
          for (int i = 0; i < index - 1; i++) curr = curr->next;
          temp = curr->next;
          curr->next = temp->next;
      }
      free(temp);
      obj->size--;
  }
  
  void myLinkedListFree(MyLinkedList* obj) {
      Node* curr = obj->head;
      while (curr) {
          Node* temp = curr;
          curr = curr->next;
          free(temp);
      }
      free(obj);
  }
    class MyLinkedList {
  private:
      struct Node {
          int val;
          Node* next;
          Node(int x) : val(x), next(nullptr) {}
      };
      Node* head;
      int size;
  
  public:
      MyLinkedList() : head(nullptr), size(0) {}
  
      int get(int index) {
          if (index < 0 || index >= size) return -1;
          Node* curr = head;
          for (int i = 0; i < index; i++) curr = curr->next;
          return curr->val;
      }
  
      void addAtHead(int val) {
          Node* node = new Node(val);
          node->next = head;
          head = node;
          size++;
      }
  
      void addAtTail(int val) {
          Node* node = new Node(val);
          if (!head) head = node;
          else {
              Node* curr = head;
              while (curr->next) curr = curr->next;
              curr->next = node;
          }
          size++;
      }
  
      void addAtIndex(int index, int val) {
          if (index < 0 || index > size) return;
          if (index == 0) return addAtHead(val);
          if (index == size) return addAtTail(val);
          Node* node = new Node(val);
          Node* curr = head;
          for (int i = 0; i < index - 1; i++) curr = curr->next;
          node->next = curr->next;
          curr->next = node;
          size++;
      }
  
      void deleteAtIndex(int index) {
          if (index < 0 || index >= size) return;
          Node* temp;
          if (index == 0) {
              temp = head;
              head = head->next;
          } else {
              Node* curr = head;
              for (int i = 0; i < index - 1; i++) curr = curr->next;
              temp = curr->next;
              curr->next = temp->next;
          }
          delete temp;
          size--;
      }
  };
    class MyLinkedList {
      private class Node {
          int val;
          Node next;
          Node(int val) { this.val = val; }
      }
  
      private Node head;
      private int size;
  
      public MyLinkedList() {
          head = null;
          size = 0;
      }
  
      public int get(int index) {
          if (index < 0 || index >= size) return -1;
          Node curr = head;
          for (int i = 0; i < index; i++) curr = curr.next;
          return curr.val;
      }
  
      public void addAtHead(int val) {
          Node node = new Node(val);
          node.next = head;
          head = node;
          size++;
      }
  
      public void addAtTail(int val) {
          Node node = new Node(val);
          if (head == null) head = node;
          else {
              Node curr = head;
              while (curr.next != null) curr = curr.next;
              curr.next = node;
          }
          size++;
      }
  
      public void addAtIndex(int index, int val) {
          if (index < 0 || index > size) return;
          if (index == 0) addAtHead(val);
          else if (index == size) addAtTail(val);
          else {
              Node node = new Node(val);
              Node curr = head;
              for (int i = 0; i < index - 1; i++) curr = curr.next;
              node.next = curr.next;
              curr.next = node;
              size++;
          }
      }
  
      public void deleteAtIndex(int index) {
          if (index < 0 || index >= size) return;
          if (index == 0) head = head.next;
          else {
              Node curr = head;
              for (int i = 0; i < index - 1; i++) curr = curr.next;
              curr.next = curr.next.next;
          }
          size--;
      }
  }
    
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def get(self, index):
        if index < 0 or index >= self.size:
            return -1
        curr = self.head
        for _ in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val):
        node = Node(val)
        node.next = self.head
        self.head = node
        self.size += 1

    def addAtTail(self, val):
        node = Node(val)
        if not self.head:
            self.head = node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = node
        self.size += 1

    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return
        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            node = Node(val)
            curr = self.head
            for _ in range(index - 1):
                curr = curr.next
            node.next = curr.next
            curr.next = node
            self.size += 1

    def deleteAtIndex(self, index):
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
        else:
            curr = self.head
            for _ in range(index - 1):
                curr = curr.next
            curr.next = curr.next.next
        self.size -= 1
  
    public class MyLinkedList {
      private class Node {
          public int val;
          public Node next;
          public Node(int val) {
              this.val = val;
          }
      }
  
      private Node head;
      private int size;
  
      public MyLinkedList() {
          head = null;
          size = 0;
      }
  
      public int Get(int index) {
          if (index < 0 || index >= size) return -1;
          Node curr = head;
          for (int i = 0; i < index; i++) curr = curr.next;
          return curr.val;
      }
  
      public void AddAtHead(int val) {
          Node node = new Node(val);
          node.next = head;
          head = node;
          size++;
      }
  
      public void AddAtTail(int val) {
          Node node = new Node(val);
          if (head == null) head = node;
          else {
              Node curr = head;
              while (curr.next != null) curr = curr.next;
              curr.next = node;
          }
          size++;
      }
  
      public void AddAtIndex(int index, int val) {
          if (index < 0 || index > size) return;
          if (index == 0) AddAtHead(val);
          else if (index == size) AddAtTail(val);
          else {
              Node node = new Node(val);
              Node curr = head;
              for (int i = 0; i < index - 1; i++) curr = curr.next;
              node.next = curr.next;
              curr.next = node;
              size++;
          }
      }
  
      public void DeleteAtIndex(int index) {
          if (index < 0 || index >= size) return;
          if (index == 0) head = head.next;
          else {
              Node curr = head;
              for (int i = 0; i < index - 1; i++) curr = curr.next;
              curr.next = curr.next.next;
          }
          size--;
      }
  }

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us