Efficient Implementation of Linked Lists in NestJS
Tags: datastructures, typescript, nestjs, backend
Published: 2024-07-12 16:56:21

**Introduction**

NestJS, a progressive Node.js framework, offers a robust platform for building efficient and scalable server-side applications. Understanding and implementing efficient data structures can significantly improve the performance and maintainability of your applications. This article focuses on linked lists, specifically Single Linked List(SLL), a fundamental data structure, and how to effectively use them in NestJS.

**Understanding Linked Lists**

**Overview:**

A linked list is a linear data structure where each element (node) contains a reference (link) to the next element in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, making them efficient for insertions and deletions.

**Types of Linked Lists:**

1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both the next and the previous nodes.
3. Circular Linked List: The last node points back to the first node, forming a circle.

**Implementing a Singly Linked List in NestJS**

1. **Node Class:**
Each node in a linked list contains data and a reference to the next node.

```
export class ListNode {
  constructor(
    public data: any,
    public next: ListNode | null = null,
  ) {}
}
```

2. **Linked List Class:**
The linked list class manages the nodes and provides methods for common operations.

```
export class LinkedList {
  private head: ListNode | null = null;

  add(data: any): void {
    const newNode: ListNode = new ListNode(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current: ListNode = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  remove(data: any): void {
    if (!this.head) {
      return;
    }

    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }

    let current: ListNode = this.head;
    while (current.next && current.next.data !== data) {
      current = current.next;
    }

    if (current.next) {
      current.next = current.next.next;
    }
  }

  find(data: any): ListNode | null {
    let current: ListNode = this.head;
    while (current && current.data !== data) {
      current = current.next;
    }
    return current;
  }

  print(): void {
    let current: ListNode = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}
```

3. **NestJS Service:**
Integrate the linked list into a NestJS service to encapsulate its operations.

```
@Injectable()
export class LinkedListService {
  private linkedList: LinkedList = new LinkedList();

  addElement(data: any): void {
    this.linkedList.add(data);
  }

  removeElement(data: any): void {
    this.linkedList.remove(data);
  }

  findElement(data: any): ListNode {
    return this.linkedList.find(data);
  }

  getElements(): void {
    return this.linkedList.print();
  }
}
```

**Controller Integration**

Create a controller to expose the linked list operations through API endpoints.

```
@Controller('linked-list')
export class LinkedListController {
  constructor(private readonly linkedListService: LinkedListService) {}

  @Post('add')
  addElement(@Body('data') data: any) {
    this.linkedListService.addElement(data);
    return { message: 'Element added successfully' };
  }

  @Delete('remove')
  removeElement(@Body('data') data: any) {
    this.linkedListService.removeElement(data);
    return { message: 'Element removed successfully' };
  }

  @Get('find')
  findElement(@Body('data') data: any) {
    const element = this.linkedListService.findElement(data);
    return { element };
  }

  @Get()
  getElements() {
    this.linkedListService.getElements();
    return { message: 'Elements printed successfully' };
  }
}
```

**Optimizing Linked Lists**

- Time Complexity:
  - Insertion: O(1) if inserting at the head; O(n) if inserting at the 
    tail.
  - Deletion: O(1) if deleting the head; O(n) if deleting another node.
  - Search: O(n).

**Use Cases:**
  - Use linked lists for scenarios where frequent insertions and 
    deletions are required.
  - Suitable for implementing queues, stacks, and other dynamic data 
    structures.

**Conclusion**

Understanding and implementing linked lists in NestJS can greatly enhance the performance and scalability of your applications. By integrating linked lists into NestJS services and controllers, you can create robust and efficient solutions for various use cases. Experiment with these implementations in your projects to see the benefits firsthand.

My way is not the only way!