<h1
style="
display: flex;
align-items: center;
justify-content: center;"
>
DSaA Lab 2 - Linked Lists
</h1>

<h4 style="text-align: center;">
The Islamic University of Gaza<br>
Engineering Faculty<br>
Department of Computer Engineering
</h4>

<font color="#ec53c4">
Prepared by:
Eng. Ahmad Albarasy
</font>
<br>
<font color="#ec53c4">
Under the supervision of:
Prof. Ahmad Mahdi
</font>

---

In this lab, we are going to learn about Linked Lists. What are they, how can we implement them, their key terminology and types, and how they can be utilized to solve intersting problems and to implement other complex data structures.

## Definition

### What is a Linked List?

A linked list is a linear data structure that stores elements in a sequence of chained nodes. Each node is an object that has 2 attributes: the data it holds, and a pointer to the next node.


### Key Terminology

To deal with any data structure, you should understand its terminology first:


* **A Node**: A node is an object which holds 2 values:
1. **The data it holds** (String, int, Object, etc.)
2. **A pointer to the next (or previous) Node**

class Node<T> {
  T data;
  Node<T> next;

  public Node(T data) {
      this.data = data;
      this.next = null;
  }
  
  public Node<T> getNext(){
    return next;
  }
  
  public void setNext(Node<T> node){
    this.next = node;
  }
  
}

* **The Head**: the head of the linked list is basically a pointer to its first node, which serves as an entry point for traversing the linked list and performing operations on its elements

* **The Tail**: the tail of the linked list is a pointer to its last element. In some implementations, especially in singly linked lists, this pointer is not included, but in other types of linked lists where traversal often happens from either end of the list, its crucial to include it to improve efficiency.

### How is it different from an array?


The key difference between arrays and linked lists is that arrays store elements in contiguous memory locations, allowing for constant-time access `O(1)` to any element by index.

In contrast, the nodes of a linked list are not stored in a contiguous fashion, but rather in a series of chained objects, where each object has a pointer that points to the next node (where each node is stored on the heap is an advanced topic which is beyond the scope of this course). This makes it costly to access a specific node, which, in the worst case scenario (accessing the last element without having a `tail` pointer), could take up to `O(n)`, where `n` is the length of the linked list.

However, linked lists have significant advantages in specific operations. For example, removing the first element in the list could simply be done by advancing the head pointer to the second element, effectively removing the first element. The garbage collector will take care of freeing the deleted node's memory.

## Types of Linked Lists

### Singly Linked List

Its a linked list where each node has only **one pointer** to the next node, meaning it can only be accessed from one end and traversed in one direction.

By convention, the `next` pointer of the last node is set to `null`, indicating the end of the list.


#### Implementation in Java:

public class SinglyLinkedList<E> {

  private static class Node<E> {
    private E element;
    private Node<E> next;

    public Node(E e, Node<E> n) {
      element = e;
      next = n;
    }

    public E getElement() {
      return element;
    }

    public Node<E> getNext() {
      return next;
    }

    public void setNext(Node<E> n) {
      next = n;
    }
  }

  private Node<E> head = null;
  private Node<E> tail = null;
  private int size = 0;

  public SinglyLinkedList() {}

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public E first() {
    if (isEmpty()) return null;
    return head.getElement();
  }

  public E last() {
    if (isEmpty()) return null;
    return tail.getElement();
  }

  public void addFirst(E e) {
    head = new Node<>(e, head);
    if (size == 0)
      tail = head;
    size++;
  }

  public void addLast(E e) {
    Node<E> newest = new Node<>(e, null);
    if (isEmpty())
      head = newest;
    else
      tail.setNext(newest);
    tail = newest;
    size++;
  }

  public E removeFirst() {
    if (isEmpty()) return null;
    E answer = head.getElement();
    head = head.getNext();
    size--;
    if (size == 0)
      tail = null;
    return answer;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder("(");
    Node<E> walk = head;
    while (walk != null) {
      sb.append(walk.getElement());
      if (walk.getNext() != null)
        sb.append(", ");
      walk = walk.getNext();
    }
    sb.append(")");
    return sb.toString();
  }
}

#### Some Real World Applications

Singly linked lists are widely used to solve a diverse set of problems. One of their main use cases is to implement other data structures such as stacks, which we will see in upcoming labs.

Furthermore, In operating systems, imagine your computer has a pool of free memory blocks, and you need to keep track of which parts of memory are available for use. We can implement a **free list** structure, where each node represents a free memory block.

Each node stores the size of the memory block, and a pointer to the next free memory block:


---

### Doubly Linked List

A doubly linked list differs from a singly linked list in one key aspect, which is that each node has **2 pointers**: `next`, which points to the next node, and `previous`, which points to the previous node. This allows traversing the list in both directions, however, this doesn't mean we should use it always over a singly linked list,because it requires extra memory for the additional pointer and slightly more complex pointer updates during insertions and deletions.

#### Implementation in Java

class DoublyLinkedList<E> {

  public static class Node<E> {

    private E element;
    private Node<E> prev;
    private Node<E> next;

    public Node(E e, Node<E> p, Node<E> n) {
      element = e;
      prev = p;
      next = n;
    }

    public E getElement() {
      return element;
    }

    public void setElement(E element) {
      this.element = element;
    }

    public Node<E> getPrev() {
      return prev;
    }

    public Node<E> getNext() {
      return next;
    }

    public void setPrev(Node<E> p) {
      prev = p;
    }

    public void setNext(Node<E> n) {
      next = n;
    }
  }

  private Node<E> header;
  private Node<E> trailer;
  private int size = 0;

  public DoublyLinkedList() {
    header = new Node<>(null, null, null);
    trailer = new Node<>(null, header, null);
    header.setNext(trailer);
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public Node<E> getHead() {
    if (isEmpty()) {
      return null;
    }
    return header.getNext();
  }

  public Node<E> getTail() {
    if (isEmpty()) {
      return null;
    }
    return trailer.getPrev();
  }

  public E first() {
    if (isEmpty()) {
      return null;
    }
    return header.getNext().getElement();
  }

  public E last() {
    if (isEmpty()) {
      return null;
    }
    return trailer.getPrev().getElement();
  }

  public void addFirst(E e) {
    addBetween(e, header, header.getNext());
  }

  public void addLast(E e) {
    addBetween(e, trailer.getPrev(), trailer);
  }

  public E removeFirst() {
    if (isEmpty()) {
      return null;
    }
    return remove(header.getNext());
  }

  public E removeLast() {
    if (isEmpty()) {
      return null;
    }
    return remove(trailer.getPrev());
  }

  private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
    Node<E> newest = new Node<>(e, predecessor, successor);
    predecessor.setNext(newest);
    successor.setPrev(newest);
    size++;
  }

  public E remove(Node<E> node) {
    Node<E> predecessor = node.getPrev();
    Node<E> successor = node.getNext();
    predecessor.setNext(successor);
    successor.setPrev(predecessor);
    size--;
    return node.getElement();
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder("(");
    Node<E> walk = header.getNext();
    while (walk != trailer) {
      sb.append(walk.getElement());
      if (walk.getNext() != trailer) {
        sb.append(", ");
      }
      walk = walk.getNext();
    }
    sb.append(")");
    return sb.toString();
  }
}

#### Real World Example

Doubly linked lists are used in a wide range of applications. For example, in text editors, a doubly linked list can be used to store characters or lines of text.

Each node represents a character (or line) and contains pointers to both its previous and next nodes. This structure allows the cursor to move efficiently in both directions and makes insertions or deletions at arbitrary positions extremely fast, only pointer adjustments are needed.

For instance, when a user types or deletes a character, the editor can simply insert or remove a node at the cursor position without having to shift large blocks of text, as would be required in an array-based approach.

---

### Circular Linked List

A circular linked list is a variation of a linked list in which the last node’s pointer does not point to `null`, but instead points back to the first node.

This creates a circular chain of nodes, allowing continuous traversal through the list without ever reaching an end.


Circular linked lists can be singly or doubly linked, and they are often used in applications that require cyclic iteration, such as round-robin scheduling or buffering systems.

#### Implementation in Java

public class CircularlyLinkedList<E> {

  private static class Node<E> {
    private E element;
    private Node<E> next;

    public Node(E e, Node<E> n) {
      element = e;
      next = n;
    }

    public E getElement() {
      return element;
    }

    public Node<E> getNext() {
      return next;
    }

    public void setNext(Node<E> n) {
      next = n;
    }
  }

  private Node<E> tail = null;
  private int size = 0;

  public CircularlyLinkedList() {}

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public E first() {
    if (isEmpty()) return null;
    return tail.getNext().getElement(); // head
  }

  public E last() {
    if (isEmpty()) return null;
    return tail.getElement();
  }

  public void rotate() {
    if (tail != null)
      tail = tail.getNext();
  }

  public void addFirst(E e) {
    if (isEmpty()) {
      tail = new Node<>(e, null);
      tail.setNext(tail);
    } else {
      Node<E> newest = new Node<>(e, tail.getNext());
      tail.setNext(newest);
    }
    size++;
  }

  public void addLast(E e) {
    addFirst(e);
    tail = tail.getNext();
  }

  public E removeFirst() {
    if (isEmpty()) return null;
    Node<E> head = tail.getNext();
    if (head == tail)
      tail = null;
    else
      tail.setNext(head.getNext());
    size--;
    return head.getElement();
  }

  @Override
  public String toString() {
    if (isEmpty()) return "()";
    StringBuilder sb = new StringBuilder("(");
    Node<E> walk = tail.getNext();
    for (int i = 0; i < size; i++) {
      sb.append(walk.getElement());
      if (i < size - 1)
        sb.append(", ");
      walk = walk.getNext();
    }
    sb.append(")");
    return sb.toString();
  }
}

#### Some Real world applications

Circular linked lists are commonly used in situations where data needs to be processed in a continuous, cyclic manner.

A classic example is round-robin scheduling in operating systems, where each process is given an equal time slice in a repeating cycle.

Another example could be a game where players take turns. Each player is a node in a circular linked list, and the turn rotates continuously from one player to the next, looping back to the first player after the last one.

## Tasks

### Task 1 (6 points)

For this task, you are going to build a class called `LinkedString` which represents a string using a doubly linked list.

**Your class should have the following 2 constructors:**

* `LinkedString()` Initializes an empty linked string
* `LinkedString(String str)` Initializes the linked string from a given `String` object

**Your class should have the follwoing methods:**

* `size()` Returns the length of the linked string
* `toString()` Converts the linked string into a regular Java `String` object
* `reverse()` Reverses the linked string in-place, without creating a new list
* `deleteCharAt(index i)` Deletes the character at the specified index `i`
* `append(String str)` Appends the given String `str` to the linked string
* `append(LinkedString str)` Appends the given LinkedString `str` to the linked string

**Use the following code to implement your solution:**

/* make sure to add both this package identifier
 * and the imoprt statement before you submit your solution
 *  to GradeScope. Remove them while testing locally */
package com.gradescope.labTwo;
import com.gradescope.labTwo.tests.DoublyLinkedList;

public class LinkedString {

    private final DoublyLinkedList<Character> list;

    public LinkedString(){
        this.list = new DoublyLinkedList<>();
    }

    public LinkedString(String str){
        this.list = new DoublyLinkedList<>();
        // continue implementing this constructor
    }

    public int size(){
        // implement this method
        return 0;
    }

    public void append(String str){
        // implement this method
    }

    public void append(LinkedString str){
        // implement this method
    }

    public DoublyLinkedList.Node<Character> getFirstCharacterNode(){
        // implement this method
        return null; // just a dummy return
    }

    public void reverse(){
        // implement this method
    }

    public void deleteCharAt(int index){
        // implement this method
    }

    @Override
    public String toString(){
        // implement this method
        return null; // just a dummy return
    }
}

**Use the following code to test your solution:**

public class LinkedStringTests {
    public static void main(String[] args) {

        System.out.println("===== TEST 1: Creating empty LinkedString =====");
        LinkedString empty = new LinkedString();
        System.out.println("Expected size = 0");
        System.out.println("Actual size   = " + empty.size());
        System.out.println();

        System.out.println("===== TEST 2: Creating from normal String =====");
        LinkedString hello = new LinkedString("Hello");
        System.out.println("Expected size = 5");
        System.out.println("Actual size   = " + hello.size());
        System.out.println("Expected string = Hello");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println();

        System.out.println("===== TEST 3: append(String) =====");
        hello.append(" World");
        System.out.println("Expected string = Hello World");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println("Expected size = 11");
        System.out.println("Actual size   = " + hello.size());
        System.out.println();

        System.out.println("===== TEST 4: append(LinkedString) =====");
        LinkedString exclamation = new LinkedString("!");
        hello.append(exclamation);
        System.out.println("Expected string = Hello World!");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println("Expected size = 12");
        System.out.println("Actual size   = " + hello.size());
        System.out.println();

        System.out.println("===== TEST 5: reverse() =====");
        hello.reverse();
        System.out.println("Expected string = !dlroW olleH");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println();

        System.out.println("===== TEST 6: deleteCharAt(middle) =====");
        hello.deleteCharAt(1);
        System.out.println("Expected string = !lroW olleH");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println("Expected size = 11");
        System.out.println("Actual size   = " + hello.size());
        System.out.println();

        System.out.println("===== TEST 7: deleteCharAt(first) =====");
        hello.deleteCharAt(0);
        System.out.println("Expected string = lroW olleH");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println();

        System.out.println("===== TEST 8: deleteCharAt(last) =====");
        hello.deleteCharAt(hello.size() - 1);
        System.out.println("Expected string = lroW olle");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println();

        System.out.println("===== TEST 9: reverse() again (odd size) =====");
        hello.reverse();
        System.out.println("Expected string = ello Worl");
        System.out.println("Actual string   = " + hello.toString());
        System.out.println();

        System.out.println("===== ALL TESTS EXECUTED =====");
    }
}

---

### Task 2 (4 points)

You are given the heads of two sorted linked lists `list1` and `list2`.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.


Question link on [LeetCode](https://leetcode.com/problems/merge-two-sorted-lists)

> **Example 1:**
Input: list1 = `[1,2,4]`, list2 = `[1,3,4]`
Output: `[1,1,2,3,4,4]`

> **Example 2:**
Input: list1 = `[]`, list2 = `[]`
Output: `[]`

> **Example 3:**
Input: list1 = `[]`, list2 = `[0]`
Output: `[0]`

Constraints:
* The number of nodes in both lists is in the range `[0,50]`.
* `-100 <= Node.val <= 100`
* Both `list1` and `list2` are sorted in non-decreasing order.

**Use the following code to implement your solution:**

/* make sure to add this package identifier before you
 * submit your solution to GradeScope. Remove it while testing locally */
package com.gradescope.labTwo;
import com.gradescope.labTwo.tests.SinglyLinkedList;

public class TaskTwo {
  public static SinglyLinkedList.Node<Integer> mergeTwoLists(
    SinglyLinkedList.Node<Integer> l1,
    SinglyLinkedList.Node<Integer> l2
  ) {
        // implement your solution here
    }
}

You are going to solve this question on LeetCode so you get more used to it :)

---
<div
style="display: flex;
align-items: center;
justify-content: center;"
>
Happy Coding 🙂
</div>