Day 3

[githubdudu]

Review of yesterday's

My possible solution is on this branch: https://github.com/githubdudu/react-study-group/tree/day2-solution

1. This way of addLast is very inefficient because we have to iterator all the elements in the list.

    @Override
    public void addLast(Object item) {
        add(size, item);
    }

We shall directly use sentinel.prev to get the last element. By using sentinel, we implement the DLL as a circle.

    @Override
    public void addLast(V item) {
        // TODO: make this method as efficient as possible
        Node newNode = new Node(item, sentinel.prev, sentinel);
        sentinel.prev.next = newNode;
        sentinel.prev = newNode;
        size++;
    }

2. We can utilize the generic to finish task 2. Object type is not a better way. :-)

   

3. You may notice there is an error in JavaScript version. To fix this error, we must either rename the size() function or rename the this.size property.
   This is because in the class of JS, property and function are all treated as objects. An override will happen if there is a same-name declaration.

[githubdudu]

Some questions or tasks TODAY

1. Figure out how to run your JS file dll.js on the console. Have a test if you haven't tried the bug/error. Try to fix it.
2. Using big O notation to summarise the time complexity of each method/operation of DLL. What is the advantage of DLL? What is the disadvantage of DLL?
3. JS: Figure out what a prototype is and how we could define or rewrite the methods/ functions of a class via prototype.
4. Learn the JS Object https://javascript.info/object. Pay attention to :
   4.1 how to create a property?
   4.2 how to remove a property?
   4.3 which kind of property name is valid?
   4.4 What is for in? Think about how to implement a method/ function in dll.js and make it support enhanced for in.
5. Finish exercises on this page: https://javascript.info/object

[jinwookuk]

Day 3:

1. To run dll.js on the console, run node dll.js . The error was caused because there was a conflict in naming of size method and property. In JS, when this occurs, it prioritises property instead of method, so I renamed size() method to getSize().

2. DLL methods and time complexity: 1. add(index, value) O(n)
   2. addFirst(value) O(1)
   3. addLast(value) O(1)
   4. get(index) O(n)
   5. getFirst() O(1)
   6. getLast() O(1)
   7. remove(index) O(n)
   8. removeFirst() O(1)
   9. removeLast() O(1)
   10. getSize() O(1)
   11. isEmpty() O(1)
   12. indexOf(value) O(n)
   13. contains(value) O(n)
   14. toString() O(n)
   15. arrayToDLL(arr) O(n)

• The advantage of DLL is that traversing the nodes bidirectionally allows for inserting & removing of nodes with time complexity of O(1), without having to traverse all of its nodes.

• The disadvantage of DLL would be that it consumes more memory as each node contains pointers to its previous node and its next node. It also requires more complex management of those extra pointers.

3. A prototype in JS is an object containing methods & properties which is a key feature of OOP. JS objects can inherit its properties from their prototype and every JS objects have its prototype. It allows adding methods and properties to a prototype object, and these will be available to all instances of the object created by that function, which reduces memory usage when creating many instances as only one copy of each method exists in memory.

   It can be rewritten in this format:

   DLL.prototype.add = function(index, value){
   		if (index < 0 || index > this.size) {
         throw new RangeError("Index out of bounds");
       }
   
       let current = this.sentinel;
       for (let i = 0; i < index; i++) {
         current = current.next;
       }
   
       const newNode = new Node(value, current, current.next);
       current.next.prev = newNode;
       current.next = newNode;
       this.size++;
   }
   

4. How to create a property?

   let object = {
   	a: "john",
   	b: "doe",
   	}
   	
   or
   
   let object = {};
   object.a = "john";
   object.b = "doe";

   How to remove a property?

   delete object.a;
   delete object.b;

   Which kind of property name is valid?

   • Quoted multiwords or any word, including “for”, “let”, “return”, etc.

   What is for in? Think about how to implement a method/ function in dll.js and make it support enhanced for in.

   • for in is a loop which executes the body for each key among object properties.

   //Not sure about this question... something like this? Doesn't seem right though D:

indexOf(value) {
for (const node in DLL){
if (node == value){
return node.index?
}
return -1;
}
```

5. Tasks:

   //1
   let user = {}
   user.name: "John";
   user.surname: "Smith";
   user.name = "Pete";
   delete user.name;
   
   //2
   function isEmpty(obj){
   	for (let prop in obj){
   		return false;
   	}
   	return true;
   }
   
   //3
   let salaries = {
     John: 100,
     Ann: 160,
     Pete: 130
   }
   function sumSalaries(salaries){
   	let sum = 0;
   	for (key in salaries){
   		sum += salaries[key];
   	}
   	return sum;
   }
   
   //4
   let menu = {
     width: 200,
     height: 300,
     title: "My menu"
   };
   function multiplyNumeric(menu){
   	for (key in menu){
   		if (typeof menu[key] == "number"){
   			menu[key] *= 2;
   		}
   	}
   }