Day 1

[githubdudu]

23 Feb.

Let’s start with one key feature of React: hooks. Nowadays, React has been introducing more hooks APIs. Understanding the hooks is crucial.

Before we look into what hooks are, what the syntax of hooks are, and how to use them, I’ll give you one short answer for now: single-linked list or double-linked list is one of the data structures that hooks are implemented with.

We’ll figure out what are single-linked list and double-linked list and how to implement them. During this, we will also crack the related JS key features that are necessary to finish the goal.

Study goal:

• concept: Single-linked list, double-linked list
• concept: time complexity and space complexity
• concept: big O notation and big Ω notation.

Questions:

1. Using a search engine or ChatGPT to find out what is the double-linked list.
2. Using a search engine or ChatGPT to find out what is the single-linked list.
3. Know basic concepts of time complexity and space complexity.
4. Thinking about how to implement a DLL (double-linked list) in Java? What about Javascript? (Optional. Answer with the code snippets )

@zep, @tiffini, @chris, @andres, @karson, Please write down your answers below using your own words. 😄
It is important that everyone participates and contributes.

[Karson421]

1.single-linked list: a data structure, each node contain data, and links to bind each node one by one. it's unidirectional.
2.double-linked list: almost same as single one, except it's bidirectional.
3.time and space complexities are both a way to describe how the time or memory is used when data is inputed
big O notation and big Ω notation: a theoretical concept, cannot directly write in code, they represent the upper and lower bounds of time or space.
4.不懂啊不懂啊 概念懂了 但gpt给我写的代码 我完全看不懂啊啊啊啊啊🤯，都是没学过的语法， Node是啥我都不知道 感觉这list没必要呀 就是用来传输数据的一种data structure吗 。简化数据传输的一种方式structure吗 😭。 gpt给我的 js的例子也用了class， js里也有class， constructor吗。

class Node {
  int data;
  Node prev;
  Node next;

  Node(int data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  Node head, tail;

  DoublyLinkedList() {
    this.head = null;
    this.tail = null;
  }

  void add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = tail = newNode;
    } else {
      tail.next = newNode;
      newNode.prev = tail;
      tail = newNode;
    }
  }

  void remove(int data) {
    Node current = head;
    while (current != null) {
      if (current.data == data) {
        if (current.prev != null) current.prev.next = current.next;
        if (current.next != null) current.next.prev = current.prev;
        if (current == head) head = current.next;
        if (current == tail) tail = current.prev;
      }
      current = current.next;
    }
  }
}

[tiff777]

1. Double linked list is a data structure which each node has a previous node pointer and next node pointer to connect each other (like a train). This structure can help developer easier to modify data in the list.

2. Single linked list also is a data structure. However, different from double linked list, it only contains next node pointer. So, it only can move in one direction and is the simplest type of linked list.

3. Time complexity refers to the amount of time taken by the algorithm to run while space complexity refers to the amount of memory that algorithm needs to run. Both depend to the size of the input.
   Big O notation can be used in both performance criteria in order to measure the worst-case scenario while Big Ω Notation is for the best case. By reading these, we can know the range of performance of the algorithm when the input size increase.

4. Java:
   ListNode class:

public class ListNode {

    private int data;

    private ListNode previous;
    private ListNode next;

    public ListNode(int data) {
        this.data = data;
        previous = null;
        next = null;
    }

    public ListNode getPrevious() {
        return previous;
    }

    public void setPrevious(ListNode previous) {
        this.previous = previous;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    public int getData() {
        return data;
    }
}

DoubleLinkedList class

public class DoubleLinkedList {
    private ListNode head;
    private ListNode tail;

    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void insertNode(int data) {
        ListNode temp = new ListNode(data);
        if (tail == null) {
            head = temp;
            tail = temp;
        } else {
            tail.setNext(temp);
            temp.setPrevious(tail);
            tail = temp;
        }
    }

    public void insertNodeSpecificPosition(int data, int position) {
        ListNode temp = new ListNode(data);
        if (position == 1) {
            temp.setNext(head);
            head.setPrevious(temp);
            head = temp;
        } else {
            ListNode currentNode = head;
            int index = 1;
            while (currentNode != null && index < position) {
                currentNode = currentNode.getNext();
                index++;
            }

            if (currentNode == null) {
                insertNode(data);
                return;
            }

            temp.setPrevious(currentNode.getPrevious());
            temp.setNext(currentNode);
            currentNode.getPrevious().setNext(temp);
            currentNode.setPrevious(temp);
        }
    }

    public void deleteNodeSpecificPosition(int position) {
        if (head == null) {
            return;
        }

        if (position == 1) {
            ListNode temp = head.getNext();
            temp.setPrevious(null);
            head = temp;
        } else {
            ListNode currentNode = head;
            int index = 1;
            while (currentNode != null && index < position) {
                currentNode = currentNode.getNext();
                index++;
            }

            if (currentNode == null) {
                System.out.println("Position is out of range");
            }

            currentNode.getPrevious().setNext(currentNode.getNext());
            currentNode.getNext().setPrevious(currentNode.getPrevious());

            currentNode.setPrevious(null);
            currentNode.setNext(null);
        }

    }

    public void printList() {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.getData() + "-> ");
            temp = temp.getNext();
        }
        System.out.println("null");
    }
}

Main

public static void main(String[] args) {
        DoubleLinkedList ddl = new DoubleLinkedList();

        ddl.insertNode(1);
        ddl.insertNode(2);
        ddl.insertNode(3);

        System.out.println("Initial list:");
        ddl.printList();

        ddl.insertNodeSpecificPosition(4, 2);
        System.out.println("After inserting a node at specific position:");
        ddl.printList();

        ddl.deleteNodeSpecificPosition(3);
        System.out.println("After deleting a node at specific position:");
        ddl.printList();
}

[githubdudu]

Thank you for your reply. 😅
My understanding of question 4:

1. OOP is a more nature way of organise code of SLL and DLL.
2. Try with Java is a good start.
3. If we use OOP, the Node class will be a great help. This class will act as the smallest storage element in SLL and DLL. It is just like one 'node' in a long chain list.

[githubdudu]

[katiezhao992]

1. Double-linked list - this refers to a list that contains the data itself (which contains in a node), with a prev pointer and a next pointer. The prev pointer holds a reference to the previous node in the list, with next pointer holds a reference to the next node in the list.

2. Single-linked list - while single linked list only contains the data/information with a next pointer, which hold reference to the next node in the list.

3. Time complexity - this refers to the time required to run an algorithm based on the input 'n'

4. Space complexity - this refers to the memory required to run an algorithm based on the input 'n'

5. to implement double linked list using Java:
   class DoublyLinkedList {
   private Node head;
   private Node tail;

   private static class Node {
   int data;
   Node next;
   Node prev;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
   

   }
   }

6. to implement double linked list using Javascript: (as compared to Java, Javascript does not require strict declaration of data type like Node, int, etc.)
   class DoublyLinkedList {
   constructor() {
   this.head = null;
   this.tail = null;
   }

   class Node {
   constructor(data) {
   this.data = data;
   this.next = null;
   this.prev = null;
   }
   }

[Aama064]

0. Linked List is a type of data structure.

1. In double-linked lists we have "nodes" which contain data (whatever kind of data you need it to contain) and a reference to the previous node and the next node in the list. The first node previous references and the last node next reference would be Null.

2. In a single-linked list we have "nodes" which contain data (whatever kind of data you need it to contain) and a reference to the next node in the list. The last node reference would be Null.

3, Time complexity refers to the time it takes and algorithm to run, and space complexity refers to the amount of memory an algorithm uses to be run. Big O notation is used to refer to the kind of growth the function experiences time wise.
Big Ω represents the best case scenario for an algorithm time wise.

4. Single linked list in Java, assuming int as the data stored in each node would be something like:

public class Node {
    int data;
    Node next;

    // Constructor to initialize the node with data
    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}

In JS:

class Node {
    constructor(data) {
    // Data part of the node
        this.data = data;   
        this.next = null;   
    }
}

Double linked list will be in Java:

class Node {

    // To store the Value or data.
    int data;

    // Reference to the Previous Node
    Node prev;
  
    // Reference to the next Node
    Node next;
  
    // Constructor
    Node(int d) {
       data = d;
       prev = next = null;      
    }
};

In JS:

class Node {
    constructor(data)
    {
        // To store the value or data.
        this.data = data;

        // Reference to the previous node
        this.prev = null;

        // Reference to the next node
        this.next = null;
    }
}

[jinwookuk]

1. A doubly linked list is a data structure where each node in the list has references to its previous node and next node, allowing for bidirectional traversal of the list. This makes the process of insertion and deletion of nodes from a list easier and quicker compared to when using an array list or singly linked list.

2. A singly linked list is a data structure where each node in the list has a reference to its next node. The insertion and deletion process is easier and quicker than using an array list.

3. Time complexity describes the time an algorithm takes to run from an input and space complexity describes the memory an algorithm requires to run from an input. Big O notation describes the worst case (upper bound) whereas big Ω notation describes the best case (lower bound). These are used for describing the range of an algorithm’s performance.

4. DLL in Java:

class DoublyLinkedList {
    private Node head;
    private Node tail;
  
    	private static class Node {
    		int data;
    		Node prev;
    		Node next;
    				
    			public Node (int data){
    				this.data = data;
    				this.prev = null;
    				this.next = null;
 }

DLL in JS:

class DoublyLinkedList {
	constructor(){
		this.head = null;
		this.tail = null;
	}

	class Node {
		constructor(data){
			this.data = data;
			this.prev = null;
			this.next = null;
		}
	}
}

[leonalu12]

1. A double-linked list is a type of linked list data structure where each node contains data and two pointers: one pointing to the next node and one pointing to the previous node. Doubly linked lists are particularly useful when you need efficient insertion and deletion of nodes and bidirectional traversal.
2. A single-linked list is a type of linked list data structure where each node contains data and a single pointer to the next node in the sequence. This makes it unidirectional, meaning you can only traverse the list in one direction. Singly linked lists are useful for simple data storage and retrieval operations, particularly when you need efficient insertion and deletion of nodes and only need to traverse the list in one direction.
3. -Time complexity refers to the amount of time an algorithm takes to complete as a function of the input size. It gives us an idea of how the running time of an algorithm increases as the input size grows. Time complexity is usually expressed using Big O notation, which describes the worst-case scenario.

• Space complexity refers to the amount of memory an algorithm uses as a function of the input size. Like time complexity, space complexity is also expressed using Big O notation. It helps us understand how the memory requirements of an algorithm grow with the input size.
• For a singly linked list, the time complexity for operations like adding or removing a node is generally O(1) if we already have a reference to the node (e.g., adding to the beginning of the list). However, finding a specific node can take O(n) time. The space complexity is O(n) because we need space for 'n' nodes.
• For a doubly linked list, the time complexity for adding or removing nodes is also O(1) if we have a reference to the node. The space complexity is O(n) due to the 'n' nodes, but each node also has an extra pointer, making the overall memory usage higher than a singly linked list.

4. how a double-linked list works in Java:

• class Node {

  int data;
  Node prev;
  Node next;

  Node(int data) {
  this.data = data;
  this.prev = null;
  this.next = null;
  }
  }

class DoublyLinkedList {
Node head, tail;

DoublyLinkedList() {
    this.head = null;
    this.tail = null;
}

void add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = tail = newNode;
    } else {
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }
}

void remove(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) {
            if (current.prev != null)
                current.prev.next = current.next;
            if (current.next != null)
                current.next.prev = current.prev;
            if (current == head)
                head = current.next;
            if (current == tail)
                tail = current.prev;
        }
        current = current.next;
    }
}

}

an example in JavaScript:
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}

class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}

add(data) {
    const newNode = new Node(data);
    if (this.head === null) {
        this.head = this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
}

remove(data) {
    let current = this.head;
    while (current !== null) {
        if (current.data === data) {
            if (current.prev !== null)
                current.prev.next = current.next;
            if (current.next !== null)
                current.next.prev = current.prev;
            if (current === this.head)
                this.head = current.next;
            if (current === this.tail)
                this.tail = current.prev;
        }
        current = current.next;
    }
}

}

[eudaimonia12]

Apology for being late for classes, Professor Dudu. Just back from a one-week holiday, and I'll be happy to see all of you guys again next week😃
My answers for Day One:

1. Single-linked list:
   A singly linked list is a fundamental data structure, it consists of nodes where each node contains a data field and a reference to the next node in the linked list. The next of the last node is null, indicating the end of the list. For me, it is like a list in which every element pointing to the next one, except the last element, which points to null.

2. Double-linked list:
   Based on a singly linked list, a doubly linked list adds a pointer to the previous element/node with each element/node. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions.

3. I learned basics of space and time complexity from CS761 last semester.
   They indicate the performance of an algorithm. Time complexity describes how long an algorithm takes in terms of the quantity of input it receives. Space complexity shows much memory (space/RAM) an algorithm requires to the quantity of input to the method. We use big O notation to estimate the worst case for an algorithm to complete its task. On the other hand, big Ω notation is used to estimate the best-case running time or space for an algorithm to solve the problem. For example, for Breadth-First Search (BFS), time complexity in big O notation is O(n), while it is Ω(n) in big Ω notation. In this case, the upper bond and the lower bond are the same because BFS needs to visit every node in the graph.

4. Implement a DLL (double-linked list) in Java and JS

Java

class Node {

// To store the Value or data.
int data;

// Reference to the Previous Node
Node prev;

// Reference to the next Node
Node next;

// Constructor
Node(int d) {
   data = d;
   prev = next = null;      
}

};
Java Script

class Node {
constructor(data)
{

    this.data = data;

    
    this.prev = null;

    
    this.next = null;
}

}