Reunderstanding Data Structures

1. Concept#

Data structures and algorithms are important foundational knowledge in computer science.
A data structure refers to a collection of data elements that have one or more specific relationships with each other. It involves the storage, organization, and management of data. Common data structures include arrays, linked lists, stacks, queues, trees, graphs, etc.
An algorithm is a sequence of steps or instructions to complete a specific task. It is essentially a description of operations on data. An algorithm mainly includes input, output, and the steps to transform input into output.
There is an inseparable relationship between data structures and algorithms. The design of an algorithm depends on the chosen data structure, and different data structures are suitable for different algorithms. The organization of data structures directly affects the efficiency of algorithms.
Mastering data structures and algorithms is crucial for developing high-quality programs. They are important criteria for evaluating a developer's technical abilities. Knowledge of data structures and algorithms is also a common focus in interviews. Many programming languages require the implementation and use of various data structures and algorithms.
Therefore, data structures and algorithms are essential foundational knowledge for every programmer, requiring extensive study, practice, and application to truly master. They are one of the core competencies that developers must focus on improving.

Composition of Data Structures#

Stack Structure
Queue
Array
Linked List
Tree
Graph
Heap Structure

1.1 Implementation of Stack Structure#

Implementation methods: based on arrays and based on linked lists. Since there are no linked lists in ts/js, it needs to be re-implemented.

interface IStack<T>{
  push():void;
  pop():void;
  size():number
  peek():T
  isEmpty():boolean
}

class Stack<T=any> implements IStack{
  private arr:T[]=[]
  push(element:T):void{
     this.arr.push(element)
  }
  pop():void{
     this.arr.pop()
  }
  size():number{
    return this.arr.length;
  }
  peek():T|undefined{
    return this.arr.pop()
  }
  isEmpty():boolean{
    return this.arr.length===0?true:false
  }
}

Interview Question 1: Implement a function to convert decimal to binary#

function toBinary(count:number):string{
  let stack =new Stack()
  let binary=""
  while(count>0){
    stack.push(count%2)   
    count= Math.floor((count/2))
  }
  while(!stack.isEmpty()){
    binary+=stack.pop()
  }
  return binary;
}

Interview Question 2: Implement symmetry for characters “(”, “{”, “[” with “}”, “]”, “)”#

For example: valid("(){}[]") true
valid("({[]})") true
valid("{()]}") false

function valid(str:string):boolean{
  const stack=new Stack()
  for(let i=0;i<str.length;i++){
    switch(str[i]){
      case "(":
        stack.push(")")
        break;
      case "{":
        stack.push("}")
        break;
      case "[": // corrected from `case "[;"`
        stack.push("]")
        break;
      default:
         if(str[i]!==stack.pop()) return false
    }
  }
  return stack.isEmpty()
}

Passing the Flower#

A group of people forms a circle and starts counting. When it stops, the person counted is eliminated, and the initial position of the last winner is determined.

Idea: Use the queue to pop in sequence. If the person is not called, push them back in.#

function findLast(arr:string[],loop:number){
  if (arr.length === 0) return -1;
  const queue=new Queue()
  for(let i=0;i<arr.length;i++){
     queue.enqueue(arr[i])
  }
  while(queue.size()>1){
    for(let i=1;i<loop;i++){
      const name=queue.dequeue()
      queue.enqueue(name)
    }
    queue.dequeue()
  }
  return queue.dequeue()
}

Linked List Structure#

Concept: Like arrays, linked lists are linear structures that can be used to store a series of elements, but the implementation mechanisms of lists and arrays are completely different. The choice of whether to use an array or a linked list depends on the operational context of the application.

Array: Allocates a fixed size of contiguous space in memory for storing data. However, when inserting elements at the front or middle of the array, all subsequent elements must be moved to the back, which can be costly if there are many elements.

Linked List: A linked list does not need to determine its size at creation. It uses the head pointer to point to the next element in the list, head=>next=>next2=>next3=>next4. When many delete or insert operations are involved, only the next pointer needs to be changed, with a time complexity of O(1). However, its drawback is evident: arrays can be indexed directly, while linked lists require traversal from the head.

Implementation of Linked List#

class Node<T=any>{
  value:T;
  next:Node<T>|null
  constructor(value:T){
    this.value=value
  }
}
class LinkList<T>{
  head:T|null=null;
  size:number=0;
  get length():number{
    return this.size
  }
  add(element):void{
    const newNode=new Node<T>(element)
    if(!this.head){
      this.head=newNode
    }else{
      let current=this.head
      while(current.next){
        current=current.next
      }
      current.next=newNode
    }
    this.size++
  }
  traverse(){
   let values:T[]=[]
   let current=this.head
   while(current){
      values.push(current.value)
      current=current.next
   }
    console.log(values.join("->"))
  }
  insert(element:T,position:number):boolean{
    if(position<0||position>this.size) return false
    const value=new Node(element)
    if(position===0){
      value.next=this.head
      this.head=value
    }else{
      let prev:Node<T>|null=null
      let current=this.head
      let index=0
      while(index++<position){
        prev= current;
        current=current.next
      }
      prev.next=value
      value.next=current
    }
    this.size++
    return true
  }
  // Remove a node at a specific position
  removeAt(position:number):T|null{
    if(position<0||position>=this.size)
      return null
    if(position===0){
      this.head=this.head.next
    }else{
      let prev:Node<T>|null=null
      let current =this.head
      let index=0
      while(index++<position){
        prev=current
        current=current.next
      }
      prev.next=current?.next ?? null
    }
    this.size--;
    return null;
  }
  // Get a node at a specific position
  get(position:number):T|null{
     if(position>this.size||position<0) return null
    let current=this.head
    let index=0
    while(index++<position){
      current=current.next ?? null
    }
    return current.value??null
  }
  // Update an element at a specific node
  update(element:T,position:number):boolean{
    if(position>=this.size||position<0) return false
    let current=this.head
    let index=0
    while(index++<position&&current){
       current=current.next
    }
    current.value=element
    return true;
  }
  // Find the index based on the element
  indexOf(element:T){
    let current=this.head
    let index=0;
    while(current){
      if(current.value===element){
        return index;
      }
      current=current.next
      index++
    }
    return -1;
  }
   remove(element: T): T | null {
    const first = this.indexOf(element);
    return this.removeAt(first);
  }
  isEmpty(): boolean {
    return this.size === 0 ? true : false;
  }
}

Interview Question: Reverse Linked List (Using Stack Structure)#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  // Only one node
  if (!head.next) return head;
  // Using stack structure
  let stack: ListNode[] = [];
  while (head) {
    stack.push(head);
    head = head.next;
  }
  const newhead: ListNode = stack.pop()!;
  let newheadCurrent = newhead;
  while (stack.length) {
    const node = stack.pop();
    newheadCurrent.next = node!;
    newheadCurrent = newheadCurrent!.next;
  }
  newheadCurrent.next = null; // The last element points to null, not the previous one, to avoid circular reference
  return newhead;
}
export {};

Reverse Linked List (Non-Recursive Implementation)#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
 if(head===null ||!head.next) return head
 let newHead:ListNode|null=null
  while(head){
    
    let current:ListNode |null=head.next
    // Let the first node point to null
    head.next=newHead
    // Move forward, and so on
    newHead=head
    head=current
  }
  return newHead;
}

Reverse Linked List (Recursive)#

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if(head===null || head.next===null) return head
  const newhead=reverseList(head.next??null)
  head.next.next=head
  head.next=null
  return newhead
}

Hash Table#

A hash table is implemented based on arrays, but it has many advantages over arrays:

Advantages#

Provides very fast lookup, deletion, and insertion operations.
Regardless of the amount of data, the time for insertion and deletion is close to constant O(1), requiring only a few mechanical instructions.
The speed of hash tables is faster than trees, allowing for almost instantaneous retrieval of target elements.
Hash tables are easier to write than tree structures.

Disadvantages#

The data structure of a hash table is unordered, so there is no fixed way to traverse elements.
In general, the keys of a hash table cannot be duplicated; the same key cannot be used to store different elements.

Essence#

Its structure is essentially an array structure, but its magic lies in the transformation of array index values. This transformation can be achieved using a hash function to obtain a hashCode.

For example, storing information for 50,000 books in an array: complexity O(n), sequentially searching for index values. Of course, binary search can reduce the complexity to O(logn), but using a hash function can directly obtain the corresponding index for each book. This function can be defined by us, for example, each book corresponds to the string "abc", and according to ASCII encoding, we get a rule: index = 97 + 98 + 99, which is the index value of the array.

It is evident that this storage method has a high rate of duplication, so solution b can solve this problem: Power of Multiplication.
For example, "abc" = 27 * 1^3 + 27 * 2^3......
However, this approach has its downsides; while it maintains uniqueness, it wastes a lot of array space. For example, "zzzzzzzzzzzzzzzzzzz" would require astronomical storage space, which is not scientific.

Thus, Chaining Method and Open Addressing Method:

Calculate the hash function for the key, obtaining the hash address.
Check the hash address; if it is empty, insert directly.
If it is not empty, check if there are elements with the same key in the linked list at that address.
If it exists, modify the content. If it does not exist, insert a new element at the head of that linked list.
When inserting a new element, create a node and insert the new node at the head of the linked list.
When searching for an element, traverse the linked list and compare the keys one by one.
The chaining method resolves conflicts, but the lookup efficiency is lower, requiring traversal of the linked list. The average search length is approximately O(1+α), where α is the length of the linked list.