LINKED LIST
I’ve mentioned before that I joined a group on MeetUp called NYC Coders!
It’s so good to be part of a like-minded community that share the same goal and help each other out.
NYC Coders is doing a 10-week session that meets every Tuesday, from 7PM EST to 10PM.
It goes by fast.
Each session (with the exception of Arrays-covered in two weeks) cover a different Data Structure.
On top of meeting every Tuesday to go over the concept, there are Pair-Programming sessions on Thursday nights, usually from 7pm EST to 8:30PM.
Here’s the schedule for this set of sessions
1. 09/14: Array Patterns
2. 09/21: Array Patterns II
3. 09/28: Recursion
4. 10/05: Linked Lists
5. 10/12: Hash Maps
6. 10/19: Stacks & Queues
7. 10/26: Binary Trees
8. 11/02: Tree Traversals
9. 11/09: Intro to Graphs
10. 11/16: Graph Traversals
I happened to miss the week of the LINKED LISTS session and was not helpful for the PAIR-PROGRAMMING Session on the following Thursday.
I tackled going over the recorded zoom video by myself but good gosh it’s quite difficult only because I did not get a chance to ask questions during the Live Zoom Session.
The Hosts allow us to ask questions any time during Live Zoom sessions, which is very nice, they welcome the interruptions. We don’t have to wait till the end of the meeting or at a specific section of the Live Zoom to ask questions.
Here are some notes from the session on Linked List
Afterwards, I’m going to attempt a LeetCode problem posted in the notes.
The process of the Live Zoom session is as follows:
* Introduction and visualizations
* Pair program on LeetCode problems
* Discussion and problem walkthroughs
WHAT IS A LINKED LIST?
· A linear data structure
· Each unit is represented as a node.
o it can have a previous and next node
· A node has pointer(s) to other nodes
· Non-contiguous in memory.
o not in the same place in memory.
o nodes don’t have to be adjacent
· Recursive structure.
o every node in a Linked List can be a linked list on its own.
— — — — — — — — — — — — — — — — — — -
WHY LINKED LISTS?
· Used for building other data structures.
o If you want to build a stack or a queue.
· Better time complexity than arrays for certain operations.
· Similar node classes are used in other data structures.
— — — — — — — — — — — — — — — — — — -
NODE CLASS
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
const head = new Node(1)
head.next = new Node(2)
head:
1 2 X
*next *next null
* the bare minimum you would need is a value and a next.
— — — — — — — — — — — — — — — — — — -
LINKED LIST METHODS
· Add: add a value to the end and return the value.
· Search: returns the node if found, or returns null if not found.
· Insert: return true if insertion is successful, or returns false if it is not successful.
· Remove: return true if removal is successful, or returns false if it is not successful.
I’m going to attempt the 206. Reverse Linked List LeetCode problem:
206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
- 5000 <= Node.val <= 5000
var reverseList = function(head) {
// base case 1: if the list is empty
if (head === null) return null;
// base case 2: if the list has 1 node
if (head.next === null) return head;
const reversedListHead = reverseList(head.next);
const nextNode = head.next;
// reverse next node’s reference (point it to current head)
nextNode.next = head;
// reverse current head (point to null)
head.next = null;
return reversedListHead;
};
This is one way how the 206. Reverse Linked List LeetCode problem can be solved.
It was quite difficult, especially since I was not able to attend the Live Zoom Session on LINKED LIST.
I’m definitely going to try to be there for the rest of the Live Zoom Sessions.
#lessonlearned
