data-structures-and-algorithms

This repository is going to be for problem solving tasks provided by ASAC team - Java Advanced course

View project on GitHub

Singly Linked List

Singly linked list is a class that has a value and a pointer that is pointing to the next element. it has a pointer pointing to the head of the list to be able to loop over using its pointer and nextNode function.

Challenge

The challenge asks us to create a linkedList class with a value and a pointer pointing to the next element and add :

  • insert method .
  • includes method : returns a true or false if it found/didn’t find a certain value in the linkedList.
  • toString: returns all elements of the linkedList in a certain format.
  • append: adds a value to the end of the linked list.
  • insertBefore: adds a newValue before a value.
  • insertAfter: add a newValue after a value.
  • DeleteValue: deletes a value from the linked list.
  • kthFromEnd: returns the value of the kth element from the tail of the linkedList.
  • linkedListZip: takes two linkedLists and returns a merged linkedList of merging them in a Zipped order as a->b->a->b.

    Whiteboard Process

    append-insertBefore-insertAfter whiteboard kthFromEnd whiteboard linkedListZip whiteboard

Approach & Efficiency

  • declare a linkedList : Time complexity O(1) , Memory complexity O(1).
  • insert: Time complexity O(1) , Memory complexity O(1).
  • includes: Time complexity O(n) , Memory complexity O(1).
  • toString: Time complexity O(n) , Memory complexity O(n).
  • append: Time complexity O(1) , Memory complexity O(1).
  • insertBefore: Time complexity O(n) , Memory complexity O(1).
  • insertAfter: Time complexity O(n) , Memory complexity O(1).
  • DeleteValue: Time complexity O(n) , Memory complexity O(1).
  • kthFromEnd : Time complexity O(k) , Memory complexity O(1).
  • linkedListZip : Time complexity O(n+m) , Memory complexity O(1).

    API

My code is able to do following functionalities publicly:

  • declare a linkedList.
  • insert: adds elements into the beginning of the linked list.
  • includes: returns true when finding a value within the linked list that exists ,and return false when searching for a value in the linked list that does not exist.
  • toString: returns a collection of all the values that exist in the linked list using.
  • append: adds a value to the end of the linked list.
  • insertBefore: adds a newValue before a value.
  • insertAfter: add a newValue after a value.
  • DeleteValue: deletes a value from the linked list.
  • kthFromEnd: returns the value of the kth element from the tail of the linkedList.
  • linkedListZip: takes two linkedLists and returns a merged linkedList of merging them in a Zipped order as a->b->a->b.