6 cấu trúc dữ liệu JavaScript bạn cần biết

6 cấu trúc dữ liệu JavaScript bạn cần biết

Khi giải quyết các vấn đề về mã hóa, hiệu quả là điều tối quan trọng – từ số giờ mã hóa đến thời gian chạy, đến dung lượng bộ nhớ dành cho một giải pháp. Rất may, các lập trình viên JavaScript sử dụng nhiều cấu trúc dữ liệu được thiết lập trước được thiết kế để giải quyết các nhu cầu chung và giải quyết các vấn đề trong thế giới thực. 

Thành thạo cấu trúc dữ liệu là yếu tố chính đánh dấu sự khác biệt giữa một lập trình viên mới và một cựu chiến binh có thể thuê được.

Có thể bạn chỉ mới bắt đầu với cấu trúc dữ liệu, hoặc có thể bạn đã viết code trong nhiều năm và chỉ cần nâng cấp. Hôm nay, tôi sẽ hướng dẫn bạn 6 cấu trúc dữ liệu hàng đầu mà bất kỳ lập trình viên JS nào cũng cần biết.

Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu, ở cấp độ cao, là các kỹ thuật lưu trữ và tổ chức dữ liệu giúp sửa đổi, điều hướng và truy cập dễ dàng hơn. Cấu trúc dữ liệu xác định cách dữ liệu được thu thập, các chức năng chúng ta có thể sử dụng để truy cập nó và mối quan hệ giữa các dữ liệu.

Cấu trúc dữ liệu được sử dụng trong hầu hết các lĩnh vực khoa học máy tính và lập trình, từ hệ điều hành đến code vanilla cơ bản cho đến trí tuệ nhân tạo.

Cấu trúc dữ liệu cho phép bạn:

  • Quản lý và sử dụng tập dữ liệu lớn
  • Tìm kiếm dữ liệu cụ thể từ cơ sở dữ liệu
  • Thiết kế các thuật toán phù hợp với các chương trình cụ thể
  • Xử lý nhiều yêu cầu từ người dùng cùng một lúc
  • Đơn giản hóa và tăng tốc độ xử lý dữ liệu

Cấu trúc dữ liệu rất quan trọng để giải quyết vấn đề hiệu quả trong thế giới thực. Xét cho cùng, cách chúng ta tổ chức dữ liệu có rất nhiều tác động đến hiệu suất và khả năng sử dụng. Trên thực tế, hầu hết các công ty hàng đầu đều yêu cầu sự hiểu biết sâu về cấu trúc dữ liệu.

Bất kỳ ai muốn bẻ khóa cuộc phỏng vấn viết mã sẽ cần phải nắm vững cấu trúc dữ liệu.

JavaScript có cấu trúc dữ liệu nguyên thủy và không nguyên thủy. 

Các cấu trúc dữ liệu nguyên thủy và kiểu dữ liệu có nguồn gốc từ ngôn ngữ lập trình. Chúng bao gồm boolean, null, number, string, v.v.

Các cấu trúc dữ liệu không nguyên thủy không được định nghĩa bởi ngôn ngữ lập trình mà là bởi người lập trình. Chúng bao gồm cấu trúc dữ liệu tuyến tính, cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động, như hàng đợi và danh sách được liên kết.

1. Mảng

Cơ bản nhất của tất cả các cấu trúc dữ liệu, một mảng lưu trữ dữ liệu trong bộ nhớ để sử dụng sau này. Mỗi mảng có một số lượng ô cố định được quyết định khi tạo và mỗi ô có một chỉ mục số tương ứng được sử dụng để chọn dữ liệu của nó. Bất cứ khi nào bạn muốn sử dụng mảng, tất cả những gì bạn cần là các chỉ số mong muốn và bạn có thể truy cập bất kỳ dữ liệu nào bên trong.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Thuận lợi

  • Đơn giản để tạo và sử dụng.
  • Khối xây dựng nền tảng cho cấu trúc dữ liệu phức tạp

Nhược điểm

  • Kích thước cố định
  • Đắt tiền để chèn / xóa hoặc gửi lại các giá trị
  • Không hiệu quả để sắp xếp

Nơi áp dụng

  • Bảng tính cơ bản
  • Trong các cấu trúc phức tạp như bảng băm

2. Hàng đợi

Về mặt khái niệm, hàng đợi tương tự như ngăn xếp; cả hai đều là cấu trúc tuần tự, nhưng xếp hàng các phần tử xử lý theo thứ tự chúng được nhập thay vì phần tử gần đây nhất.

Do đó, hàng đợi có thể được coi như một phiên bản FIFO (First In, First Out) của ngăn xếp. Chúng hữu ích như một bộ đệm cho các yêu cầu, lưu trữ từng yêu cầu theo thứ tự mà nó được nhận cho đến khi nó có thể được xử lý.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Để có hình ảnh, hãy xem xét đường hầm một làn: ô tô đầu tiên đi vào là ô tô đầu tiên đi ra. Nếu các xe khác muốn đi ra, nhưng xe đầu tiên dừng lại, thì tất cả các xe sẽ phải đợi xe đầu tiên thoát ra trước khi có thể đi tiếp.

Thuận lợi

  • Kích thước động
  • Đặt hàng dữ liệu theo thứ tự nó đã được nhận
  • Thời gian chạy thấp

Nhược điểm

  • Chỉ có thể truy xuất phần tử cũ nhất

Nơi áp dụng

  • Hiệu quả như một bộ đệm khi nhận dữ liệu thường xuyên
  • Cách thuận tiện để lưu trữ dữ liệu nhạy cảm với đơn đặt hàng, chẳng hạn như thư thoại được lưu trữ
  • Đảm bảo dữ liệu cũ nhất được xử lý trước

3. Danh sách liên kết

Danh sách được liên kết là một cấu trúc dữ liệu, không giống như ba cấu trúc trước, không sử dụng vị trí vật lý của dữ liệu trong bộ nhớ. Điều này có nghĩa là, thay vì chỉ mục hoặc vị trí, danh sách được liên kết sử dụng hệ thống tham chiếu: các phần tử được lưu trữ trong các nút có chứa một con trỏ đến nút tiếp theo, lặp lại cho đến khi tất cả các nút được liên kết.

Hệ thống này cho phép chèn và loại bỏ các mục một cách hiệu quả mà không cần phải tổ chức lại.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Thuận lợi

  • Chèn và loại bỏ hiệu quả các phần tử mới
  • Ít phức tạp hơn là tái cấu trúc một mảng

Nhược điểm

  • Sử dụng nhiều bộ nhớ hơn mảng
  • Không hiệu quả để truy xuất một phần tử cụ thể
  • Không hiệu quả để duyệt ngược danh sách

Nơi áp dụng

  • Được sử dụng tốt nhất khi dữ liệu phải được thêm và xóa liên tiếp từ các vị trí không xác định

4. Cây cối

Cây là một cấu trúc dữ liệu dựa trên quan hệ khác, chuyên thể hiện cấu trúc phân cấp. Giống như một danh sách được liên kết, các nút chứa cả phần tử dữ liệu và con trỏ đánh dấu mối quan hệ của nó với các nút ngay lập tức.

Mỗi cây có một nút “gốc”, tất cả các nút khác sẽ phân nhánh. Gốc chứa các tham chiếu đến tất cả các phần tử ngay bên dưới nó, được gọi là “các nút con” của nó. Điều này tiếp tục, với mỗi nút con, phân nhánh thành nhiều nút con hơn.

Các nút có nút con được liên kết được gọi là nút bên trong trong khi những nút không có nút con là nút bên ngoài. Một loại cây phổ biến là “cây tìm kiếm nhị phân” được sử dụng để dễ dàng tìm kiếm dữ liệu được lưu trữ.

Các hoạt động tìm kiếm này có hiệu quả cao, vì thời lượng tìm kiếm của nó không phụ thuộc vào số lượng nút mà phụ thuộc vào số cấp của cây.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Loại cây này được xác định bởi bốn quy tắc nghiêm ngặt:

  1. Cây con bên trái chỉ chứa các nút có phần tử nhỏ hơn gốc.
  2. Cây con bên phải chỉ chứa các nút có phần tử lớn hơn gốc.
  3. Các cây con trái và phải cũng phải là một cây tìm kiếm nhị phân. Họ phải tuân theo các quy tắc trên với “gốc” của cây của họ.
  4. Không thể có các nút trùng lặp, tức là không thể có hai nút nào có cùng giá trị.

Thuận lợi

  • Lý tưởng để lưu trữ các mối quan hệ phân cấp
  • Kích thước động
  • Thao tác chèn và xóa nhanh chóng
  • Trong cây tìm kiếm nhị phân, các nút được chèn được sắp xếp theo trình tự ngay lập tức.
  • Cây tìm kiếm nhị phân có hiệu quả trong việc tìm kiếm; chiều dài chỉO (chiều cao)).

Nhược điểm

  • Chậm sắp xếp lại các nút
  • Các nút con không có thông tin gì về nút cha của chúng
  • Cây tìm kiếm nhị phân không nhanh bằng bảng băm phức tạp hơn
  • Cây tìm kiếm nhị phân có thể suy biến thành tìm kiếm tuyến tính (quét tất cả các phần tử) nếu không được thực hiện với các cây con cân bằng.

Nơi áp dụng

  • Lưu trữ dữ liệu phân cấp chẳng hạn như vị trí tệp.
  • Cây tìm kiếm nhị phân rất tuyệt vời cho các tác vụ cần tìm kiếm hoặc sắp xếp thứ tự dữ liệu.

5. Đồ thị

Đồ thị là một cấu trúc dữ liệu dựa trên mối quan hệ hữu ích để lưu trữ các mối quan hệ giống như web. Mỗi nút hoặc đỉnh, như chúng được gọi trong đồ thị, có một tiêu đề (A, B, C, v.v.), một giá trị được chứa bên trong và danh sách các liên kết (được gọi là các cạnh) mà nó có với các đỉnh khác.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Trong ví dụ trên, mỗi đường tròn là một đỉnh và mỗi đường là một cạnh. Nếu được viết bằng văn bản, cấu trúc này sẽ giống như sau:

V = {a, b, c, d}

E = {ab, ac, bc, cd}

Mặc dù khó hình dung lúc đầu, nhưng cấu trúc này vô giá trong việc truyền tải biểu đồ mối quan hệ ở dạng văn bản, bất kỳ thứ gì từ mạch điện đến mạng lưới tàu.

Thuận lợi

  • Có thể nhanh chóng truyền tải hình ảnh qua văn bản
  • Có thể sử dụng để lập mô hình cho một số lượng đa dạng các đối tượng miễn là chúng chứa một cấu trúc quan hệ

Nhược điểm

  • Ở cấp độ cao hơn, văn bản có thể tốn nhiều thời gian để chuyển đổi thành hình ảnh.
  • Có thể khó nhìn thấy các cạnh hiện có hoặc bao nhiêu cạnh mà một đỉnh nhất định đã kết nối với nó

Nơi áp dụng

  • Đại diện mạng
  • Mô hình hóa các mạng xã hội, chẳng hạn như Facebook.

6. Bảng băm (Bản đồ)

Bảng băm là một cấu trúc dữ liệu phức tạp có khả năng lưu trữ lượng lớn thông tin và truy xuất các phần tử cụ thể một cách hiệu quả. Cấu trúc dữ liệu này dựa trên khái niệm về các cặp khóa / giá trị, trong đó “khóa” là một chuỗi được tìm kiếm và “giá trị” là dữ liệu được ghép nối với khóa đó.

6 cấu trúc dữ liệu JavaScript bạn cần biết

Mỗi khóa được tìm kiếm được chuyển đổi từ dạng chuỗi của nó thành một giá trị số, được gọi là hàm băm, sử dụng hàm băm xác định trước. Sau đó, băm này trỏ đến một nhóm lưu trữ – một nhóm con nhỏ hơn trong bảng. Sau đó, nó tìm kiếm trong thùng để tìm khóa đã nhập ban đầu và trả về giá trị được liên kết với khóa đó.

Thuận lợi

  • Khóa có thể ở bất kỳ dạng nào, trong khi các chỉ số của mảng phải là số nguyên
  • Chức năng tìm kiếm hiệu quả cao
  • Số lượng hoạt động không đổi cho mỗi lần tìm kiếm
  • Chi phí không đổi cho các hoạt động chèn hoặc xóa

Nhược điểm

  • Xung đột: lỗi xảy ra khi hai khóa chuyển đổi thành cùng một code băm hoặc hai code băm trỏ đến cùng một giá trị.
  • Những lỗi này có thể phổ biến và thường yêu cầu đại tu hàm băm.

Nơi áp dụng

  • Cơ sở dữ liệu lưu trữ
  • Tra cứu địa chỉ theo tên

Mỗi bảng băm có thể rất khác nhau, từ loại khóa và giá trị, đến cách hoạt động của các hàm băm của chúng. Do những khác biệt này và các khía cạnh nhiều lớp của bảng băm, nên nói chung là gần như không thể đóng gói được.

Câu hỏi phỏng vấn về cấu trúc dữ liệu

Đối với nhiều lập trình viên, cấu trúc dữ liệu là quan trọng nhất để bẻ khóa các cuộc phỏng vấn viết code Javascript . Các câu hỏi và vấn đề về cấu trúc dữ liệu là cơ bản cho các cuộc phỏng vấn viết code ngày nay. Trên thực tế, họ có rất nhiều điều để nói về khả năng tuyển dụng và tỷ lệ đầu vào của bạn với tư cách là một ứng viên.

Hôm nay, cùng mình xem xét 7 câu hỏi phỏng vấn viết code phổ biến cho cấu trúc dữ liệu JavaScript, một câu hỏi dành cho mỗi cấu trúc dữ liệu mà chúng ta đã thảo luận ở trên. Mỗi bên cũng sẽ thảo luận về độ phức tạp về thời gian của nó dựa trên lý thuyết ký hiệu BigO .

Mảng: Xóa tất cả các số nguyên chẵn khỏi một mảng

Câu lệnh vấn đề: Thực hiện một hàm  removeEven(arr) , lấy một mảng arr trong đầu vào của nó và xóa tất cả các phần tử chẵn khỏi một mảng nhất định.

Đầu vào: Một mảng các số nguyên ngẫu nhiên

[1,2,4,5,10,6,3]

Đầu ra: một mảng chỉ chứa các số nguyên lẻ

[1,5,3]
Code language: JSON / JSON with Comments (json)

Có hai cách bạn có thể giải quyết vấn đề mã hóa này trong một cuộc phỏng vấn. Hãy thảo luận về từng cái.

Giải pháp số 1: Làm điều đó “bằng tay”

function removeEven(arr) { var odds = [] for (let number of arr) { if (number % 2 != 0) // Check if the item in the list is NOT even ('%' is the modulus symbol!) odds.push(number) //If it isn't even append it to the empty list } return odds // Return the new list } console.log(removeEven([3, 2, 41, 3, 34]))
Code language: JavaScript (javascript)

Cách tiếp cận này bắt đầu với phần tử đầu tiên của mảng. Nếu phần tử hiện tại đó không chẵn, nó sẽ đẩy phần tử này vào một mảng mới. Nếu nó là chẵn, nó sẽ chuyển sang phần tử tiếp theo, lặp lại cho đến khi nó đến cuối mảng. Về độ phức tạp thời gian, vì toàn bộ mảng phải được lặp lại, giải pháp này là O(n) O(n).

Giải pháp # 2: Sử dụng hàm filter () và lambda

function removeEven(arr) { return arr.filter((v => (v % 2) != 0)) } console.log(removeEven([3,2,41,3,34]))
Code language: JavaScript (javascript)

Giải pháp này cũng bắt đầu với phần tử đầu tiên và kiểm tra xem nó có chẵn không. Nếu nó là số chẵn, nó sẽ lọc ra phần tử này. Nếu không, hãy chuyển đến phần tử tiếp theo, lặp lại quá trình này cho đến khi nó đến cuối mảng.

Bộ lọc sử dụng hàm lambda hoặc hàm mũi tên, sử dụng cú pháp ngắn hơn, đơn giản hơn. Bộ lọc lọc ra phần tử mà hàm lambda trả về false. Độ phức tạp về thời gian của giải pháp này cũng giống như độ phức tạp về thời gian của giải pháp trước đó.

Ngăn xếp: Kiểm tra các dấu ngoặc đơn cân bằng bằng cách sử dụng một ngăn xếp

Câu lệnh bài toán: Thực hiện hàm  isBalanced() lấy một chuỗi chỉ chứa các dấu ngoặc nhọn  {} , vuông  [] và tròn  () . Hàm sẽ cho chúng ta biết nếu tất cả các dấu ngoặc trong chuỗi là cân bằng. Điều này có nghĩa là mọi dấu ngoặc mở sẽ có một dấu đóng. Ví dụ,  {[]} là cân bằng, nhưng  {[}] không.

Đầu vào : Một chuỗi chỉ bao gồm  ( , ) , { , } , []

exp = "{[({})]}"
Code language: JavaScript (javascript)

Đầu ra: Trả về  False nếu biểu thức không có dấu ngoặc cân bằng. Nếu đúng, hàm sẽ trả về  True .

True
Code language: PHP (php)

Để giải quyết vấn đề này, chúng ta có thể chỉ cần sử dụng một chồng ký tự. Nhìn vào mã bên dưới để xem nó hoạt động như thế nào.

"use strict"; module.exports = class Stack { constructor() { this.items = []; this.top = null; } getTop() { if (this.items.length == 0) return null; return this.top; } isEmpty() { return this.items.length == 0; } size() { return this.items.length; } push(element) { this.items.push(element); this.top = element; } pop() { if (this.items.length != 0) { if (this.items.length == 1) { this.top = null; return this.items.pop(); } else { this.top = this.items[this.items.length - 2]; return this.items.pop(); } } else return null; } }
Code language: JavaScript (javascript)
"use strict"; const Stack = require('./Stack.js'); function isBalanced(exp) { var myStack = new Stack(); //Iterate through the string exp for (var i = 0; i < exp.length; i++) { //For every closing parenthesis check for its opening parenthesis in stack if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') { if (myStack.isEmpty()) { return false } let output = myStack.pop(); //If you can't find the opening parentheses for any closing one then returns false. if (((exp[i] == "}") && (output != "{")) || ((exp[i] == ")") && (output != "(")) || ((exp[i] == "]") && (output != "["))) { return false; } } else { //For each opening parentheses, push it into stack myStack.push(exp[i]); } } //after complete traversal of string exp, if there's any opening parentheses left //in stack then also return false. if (myStack.isEmpty() == false) { return false } //At the end return true if you haven't encountered any of the above false conditions. return true } var inputString = "{[()]}" console.log(inputString) console.log(isBalanced(inputString)) inputString = "{[([({))]}}" console.log(inputString) console.log(isBalanced(inputString))
Code language: JavaScript (javascript)

Quá trình này sẽ lặp lại trên chuỗi một ký tự tại một thời điểm. Chúng tôi có thể xác định rằng chuỗi không cân bằng dựa trên hai yếu tố:

  1. Ngăn xếp trống.
  2. Phần tử trên cùng trong ngăn xếp không phải là loại phù hợp.

Nếu một trong hai điều kiện này là đúng, chúng tôi quay trở lại  False . Nếu dấu ngoặc đơn là dấu ngoặc mở, nó được đẩy vào ngăn xếp. Nếu cuối cùng tất cả đều cân bằng, ngăn xếp sẽ trống. Nếu nó không có sản phẩm nào, chúng tôi quay trở lại  False . Vì chúng ta duyệt chuỗi exp chỉ một lần nên độ phức tạp về thời gian là O(n) .

Hàng đợi: Tạo Số nhị phân từ 1 đến n

Câu lệnh vấn đề: Thực hiện một hàm  findBin(n) , hàm này sẽ tạo ra các số nhị phân từ  1 đến  n dưới dạng một chuỗi bằng cách sử dụng một hàng đợi.

Đầu vào: Một số nguyên dương n

n = 3

Đầu ra: Trả về số nhị phân dưới dạng chuỗi từ  1 đến n

result = ["1","10","11"]
Code language: JavaScript (javascript)

Cách dễ nhất để giải quyết vấn đề này là sử dụng hàng đợi để tạo ra các số mới từ các số trước đó. Hãy phá vỡ điều đó.

"use strict"; const Queue = require('./Queue.js'); function findBin(n) { let result = []; let myQueue = new Queue(); var s1, s2; myQueue.enqueue("1"); for (var i = 0; i < n; i++) { result.push(myQueue.dequeue()); s1 = result[i] + "0"; s2 = result[i] + "1"; myQueue.enqueue(s1); myQueue.enqueue(s2); } return result; } console.log(findBin(10))
Code language: JavaScript (javascript)
"use strict"; module.exports = class Queue { constructor() { this.items = []; this.front = null; this.back = null; } isEmpty() { return this.items.length == 0; } getFront() { if (this.items.length != 0) { return this.items[0]; } else return null; } size() { return this.items.length; } enqueue(element) { this.items.push(element); } dequeue() { if (this.items.length == 0) { return null; } else { return this.items.shift(); } } }
Code language: JavaScript (javascript)

Chìa khóa là tạo các số nhị phân liên tiếp bằng cách thêm 0 và 1 vào các số nhị phân trước đó. Làm rõ,

  • 10 và 11 có thể được tạo nếu 0 và 1 được nối với 1.
  • 100 và 101 được tạo nếu 0 và 1 được nối với 10.

Khi chúng ta tạo một số nhị phân, nó sẽ được xếp vào hàng đợi để các số nhị phân mới có thể được tạo ra nếu chúng ta thêm 0 và 1 khi số đó sẽ được xếp vào hàng đợi.

Vì một hàng đợi tuân theo thuộc tính First-In First-Out , nên các số nhị phân xếp hàng đợi được định vị lại để mảng kết quả chính xác về mặt toán học.

Nhìn vào đoạn mã trên. Trên dòng 7,  1 được xếp hàng. Để tạo chuỗi số nhị phân, một số được định giá lại và được lưu trữ trong mảng  result . Trên dòng 11-12, chúng tôi thêm vào  0 và  1 để tạo ra các số tiếp theo.

Những con số mới đó cũng được xếp vào hàng 14-15. Hàng đợi sẽ nhận các giá trị số nguyên, vì vậy nó chuyển đổi chuỗi thành số nguyên khi nó được xếp vào hàng đợi.

Độ phức tạp về thời gian của giải pháp này là O(n)O(n) vì các phép toán thời gian không đổi được thực hiện trong n lần.

Danh sách được Liên kết: Đảo ngược một danh sách được liên kết

Câu lệnh vấn đề: Viết  reverse hàm lấy một danh sách liên kết đơn lẻ và đảo ngược vị trí của nó.

Đầu vào: một danh sách được liên kết đơn lẻ

LinkedList = 0->1->2->3-4

Đầu ra: một danh sách liên kết ngược

LinkedList = 4->3->2->1->0

Cách dễ nhất để giải quyết vấn đề này là sử dụng thao tác con trỏ lặp đi lặp lại.

"use strict"; const LinkedList = require('./LinkedList.js'); const Node = require('./Node.js'); //Access HeadNode => list.getHead() //Set the value of HeadNode => list.getHead() //Check if list is empty => list.isEmpty() //Insert at head => list.insertAtHead(value) //Delete at head => list.deleteAtHead() //Insert at tail => list.insertAtTail(value) //Search for element => list.search(value) //Delete by value => list.deleteVal(value) //Node class { data ; Node nextElement;} function reverse(list) { let previousNode = null; let currentNode = list.getHead(); // The current node let nextNode = null; // The next node in the list //Reversal while (currentNode != null) { nextNode = currentNode.nextElement; currentNode.nextElement = previousNode; previousNode = currentNode; currentNode = nextNode; } //Set the last element as the new head node list.setHead(previousNode); } let list = new LinkedList(); list.insertAtHead(4); list.insertAtHead(9); list.insertAtHead(6); list.insertAtHead(1); list.insertAtHead(0); list.printList(); reverse(list); list.printList();
Code language: JavaScript (javascript)
"use strict"; const Node = require('./Node.js'); module.exports = class LinkedList { constructor() { this.head = null; } //Insertion At Head insertAtHead(newData) { let tempNode = new Node(newData); tempNode.nextElement = this.head; this.head = tempNode; return this; //returning the updated list } isEmpty() { return (this.head == null); } //function to print the linked list printList() { if (this.isEmpty()) { console.log("Empty List"); return false; } else { let temp = this.head; while (temp != null) { process.stdout.write(String(temp.data)); process.stdout.write(" -> "); temp = temp.nextElement; } console.log("null"); return true; } } getHead() { return this.head; } setHead(newHead) { this.head = newHead; return this; } getListStr() { if (this.isEmpty()) { console.log("Empty List"); return "null"; } else { let st = ""; let temp = this.head while (temp != null) { st += String(temp.data); st += " -> "; temp = temp.nextElement; } st += "null"; return st; } } insertAtTail(newData) { //Creating a new Node with data as newData let node = new Node(newData); //check for case when list is empty if (this.isEmpty()) { //Needs to Insert the new node at Head this.head = node; return this; } //Start from head let currentNode = this.head; //Iterate to the last element while (currentNode.nextElement != null) { currentNode = currentNode.nextElement; } //Make new node the nextElement of last node of list currentNode.nextElement = node; return this; } search(value) { //Start from the first element let currentNode = this.head; //Traverse the list until you find the value or reach the end while (currentNode != null) { if (currentNode.data == value) { return true; //value found } currentNode = currentNode.nextElement } return false; //value not found } deleteAtHead() { //if list is empty, do nothing if (this.isEmpty()) { return this; } //Get the head and first element of the list let firstElement = this.head; //If list is not empty, link head to the nextElement of firstElement this.head = firstElement.nextElement; return this; } deleteVal(value) { let deleted = null; //True or False //Write code here //if list is empty return false if (this.isEmpty()) { return false; } //else get pointer to head let currentNode = this.head; // if first node's is the node to be deleted, delete it and return true if (currentNode.data == value) { this.head = currentNode.nextElement; return true; } // else traverse the list while (currentNode.nextElement != null) { // if a node whose next node has the value as data, is found, delete it from the list and return true if (currentNode.nextElement.data == value) { currentNode.nextElement = currentNode.nextElement.nextElement; return true; } currentNode = currentNode.nextElement; } //else node was not found, return false deleted = false; return deleted; } deleteAtTail() { // check for the case when linked list is empty if (this.isEmpty()) { return this; } //if linked list is not empty, get the pointer to first node let firstNode = this.head; //check for the corner case when linked list has only one element if (firstNode.nextElement == null) { this.deleteAtHead(); return this; } //otherwise traverse to reach second last node while (firstNode.nextElement.nextElement != null) { firstNode = firstNode.nextElement; } //since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node firstNode.nextElement = null; return this; } }
Code language: JavaScript (javascript)
"use strict"; module.exports = class Node { constructor(data) { this.data = data; this.nextElement = null; } }
Code language: JavaScript (javascript)

Chúng tôi sử dụng một vòng lặp để lặp qua danh sách đầu vào. Đối với một  current nút, liên kết của nó với  previous nút bị đảo ngược. sau đó,  next lưu trữ nút tiếp theo trong danh sách. Hãy chia nhỏ điều đó theo từng dòng.

  • Dòng 22- Lưu trữ nút current   nextElement trong next
  • Dòng 23 – Đặt  current nút  nextElement thành previous
  • Dòng 24 – Tạo  current nút mới  previous cho lần lặp tiếp theo
  • Dòng 25 – Sử dụng  next để đi đến nút tiếp theo
  • Dòng 29 – Chúng tôi đặt lại  head con trỏ để trỏ đến nút cuối cùng

Vì danh sách chỉ được duyệt một lần nên thuật toán chạy trong O (n) .

Cây: Tìm Giá trị Tối thiểu trong Cây Tìm kiếm Nhị phân

Tuyên bố vấn đề: Sử dụng  findMin(root) hàm để tìm giá trị nhỏ nhất trong Cây tìm kiếm nhị phân.

Đầu vào: một nút gốc cho cây tìm kiếm nhị phân

bst = { 6 -> 4,9 4 -> 2,5 9 -> 8,12 12 -> 10,14 } where parent -> leftChild,rightChild
Code language: PHP (php)

Đầu ra: giá trị số nguyên nhỏ nhất từ ​​cây tìm kiếm nhị phân đó

2

Hãy xem một giải pháp dễ dàng cho vấn đề này.

Giải pháp: Lặp lại findMin( )

Giải pháp này bắt đầu bằng cách kiểm tra xem gốc có phải là không  null . Nó trả về  null nếu vậy. Sau đó, nó di chuyển sang cây con bên trái và tiếp tục với nút con bên trái của mỗi nút cho đến khi đạt đến nút con ngoài cùng bên trái.

"use strict"; const BinarySearchTree = require('./BinarySearchTree.js'); const Node = require('./Node.js'); function findMin(rootNode) { if(rootNode == null) return null; else if(rootNode.leftChild == null) return rootNode.val else return findMin(rootNode.leftChild) } var BST = new BinarySearchTree(6) BST.insertBST(20) BST.insertBST(-1) console.log(findMin(BST.root))           
Code language: JavaScript (javascript)
"use strict"; const Node = require('./Node.js'); module.exports = class BinarySearchTree { constructor(rootValue) { this.root = new Node(rootValue); } insert(currentNode, newValue) { if (currentNode === null) { currentNode = new Node(newValue); } else if (newValue < currentNode.val) { currentNode.leftChild = this.insert(currentNode.leftChild, newValue); } else { currentNode.rightChild = this.insert(currentNode.rightChild, newValue); } return currentNode; } insertBST(newValue) { if(this.root==null){ this.root=new Node(newValue); return; } this.insert(this.root, newValue); } preOrderPrint(currentNode) { if (currentNode !== null) { console.log(currentNode.val); this.preOrderPrint(currentNode.leftChild); this.preOrderPrint(currentNode.rightChild); } } inOrderPrint(currentNode) { if (currentNode !== null) { this.inOrderPrint(currentNode.leftChild); console.log(currentNode.val); this.inOrderPrint(currentNode.rightChild); } } postOrderPrint(currentNode) { if (currentNode !== null) { this.postOrderPrint(currentNode.leftChild); this.postOrderPrint(currentNode.rightChild); console.log(currentNode.val); } } search(currentNode, value) { if (currentNode !== null) { if (value == currentNode.val) { return currentNode; } else if (value < currentNode.val) { return this.search(currentNode.leftChild, value) } else { return this.search(currentNode.rightChild, value) } } else { return null; } } searchBST(value) { return this.search(this.root, value); } delete(currentNode, value) { if (currentNode == null) { return false; } var parentNode; while (currentNode && (currentNode.val != value)) { parentNode = currentNode; if (value < currentNode.val) { currentNode = currentNode.leftChild; } else { currentNode = currentNode.rightChild; } } if (currentNode === null) { return false; } else if (currentNode.leftChild == null && currentNode.rightChild == null) { if(currentNode.val==this.root.val){ this.root=null; return true; } else if (currentNode.val < parentNode.val) { parentNode.leftChild = null; return true; } else { parentNode.rightChild = null; return true; } } else if (currentNode.rightChild == null) { if(currentNode.val==this.root.val){ this.root=currentNode.leftChild; return true; } else if (currentNode.leftChild.val < parentNode.val) { parentNode.leftChild = currentNode.leftChild; return true; } else { parentNode.rightChild = currentNode.leftChild; return true; } } else if (currentNode.leftChild == null) { if(currentNode.val==this.root.val){ this.root = currentNode.rightChild; return true; } else if (currentNode.rightChild.val < parentNode.val) { parentNode.leftChild = currentNode.rightChild; return true; } else { parentNode.rightChild = currentNode.rightChild; return true; } } else { var minRight = currentNode.rightChild; while (minRight.leftChild !== null) { minRight = minRight.leftChild; } var temp=minRight.val; this.delete(this.root, minRight.val); currentNode.val = temp; return true; } } }
Code language: JavaScript (javascript)
"use strict"; module.exports = class Node { constructor(value) { this.val = value; this.leftChild = null; this.rightChild = null; } }
Code language: JavaScript (javascript)

Biểu đồ: Xóa cạnh

Câu lệnh vấn đề: Thực hiện hàm removeEdge để lấy nguồn và đích làm đối số. Nó sẽ phát hiện xem có tồn tại một cạnh nào giữa chúng hay không.

Đầu vào: Biểu đồ, nguồn và đích

6 cấu trúc dữ liệu JavaScript bạn cần biết

Đầu ra: Một đồ thị có cạnh giữa nguồn và đích bị loại bỏ.

removeEdge(graph, 2, 3)
6 cấu trúc dữ liệu JavaScript bạn cần biết

Giải pháp cho vấn đề này khá đơn giản: chúng tôi sử dụng Lập chỉ mục và xóa. 

"use strict"; const LinkedList = require('./LinkedList.js'); const Node = require('./Node.js'); const Graph = require('./Graph.js'); function removeEdge(graph, source, dest){ if(graph.list.length == 0){ return graph; } if(source >= graph.list.length || source < 0){ return graph; } if(dest >= graph.list.length || dest < 0){ return graph; } graph.list.deleteVal(dest); return graph; } let g = new Graph(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(4, 0); console.log("Before removing edge") g.printGraph(); removeEdge(g, 1, 3); console.log("\nAfter removing edge") g.printGraph();
Code language: JavaScript (javascript)
"use strict"; const LinkedList = require('./LinkedList.js'); const Node = require('./Node.js'); module.exports = class Graph { constructor(vertices) { this.vertices = vertices; this.list = []; var it; for (it = 0; it < vertices; it++) { let temp = new LinkedList(); this.list.push(temp); } } addEdge(source, destination) { if (source < this.vertices && destination < this.vertices) this.list.insertAtHead(destination); return this; } printGraph() { console.log(">>Adjacency List of Directed Graph<<"); var i; for (i = 0; i < this.list.length; i++) { process.stdout.write("|" + String(i) + "| => "); let temp = this.list[i].getHead(); while (temp != null) { process.stdout.write("[" + String(temp.data) + "] -> "); temp = temp.nextElement; } console.log("null "); } } strGraph() { let str = ""; var i; for (i = 0; i < this.list.length; i++) { str = str + "|" + String(i) + "| => "; let temp = this.list[i].getHead(); while (temp != null) { str += ("[" + String(temp.data) + "] -> "); temp = temp.nextElement; } str += "null "; } return str; } }
Code language: JavaScript (javascript)
"use strict"; const Node = require('./Node.js'); module.exports = class LinkedList { constructor() { this.head = null; } //Insertion At Head insertAtHead(newData) { let tempNode = new Node(newData); tempNode.nextElement = this.head; this.head = tempNode; return this; //returning the updated list } isEmpty() { return (this.head == null); } //function to print the linked list printList() { if (this.isEmpty()) { console.log("Empty List"); return false; } else { let temp = this.head; while (temp != null) { process.stdout.write(String(temp.data)); process.stdout.write(" -> "); temp = temp.nextElement; } console.log("null"); return true; } } getHead() { return this.head; } setHead(newHead) { this.head = newHead; return this; } getListStr() { if (this.isEmpty()) { console.log("Empty List"); return "null"; } else { let st = ""; let temp = this.head while (temp != null) { st += String(temp.data); st += " -> "; temp = temp.nextElement; } st += "null"; return st; } } insertAtTail(newData) { //Creating a new Node with data as newData let node = new Node(newData); //check for case when list is empty if (this.isEmpty()) { //Needs to Insert the new node at Head this.head = node; return this; } //Start from head let currentNode = this.head; //Iterate to the last element while (currentNode.nextElement != null) { currentNode = currentNode.nextElement; } //Make new node the nextElement of last node of list currentNode.nextElement = node; return this; } search(value) { //Start from the first element let currentNode = this.head; //Traverse the list until you find the value or reach the end while (currentNode != null) { if (currentNode.data == value) { return true; //value found } currentNode = currentNode.nextElement } return false; //value not found } deleteAtHead() { //if list is empty, do nothing if (this.isEmpty()) { return this; } //Get the head and first element of the list let firstElement = this.head; //If list is not empty, link head to the nextElement of firstElement this.head = firstElement.nextElement; return this; } deleteVal(value) { let deleted = null; //True or False //Write code here //if list is empty return false if (this.isEmpty()) { return false; } //else get pointer to head let currentNode = this.head; // if first node's is the node to be deleted, delete it and return true if (currentNode.data == value) { this.head = currentNode.nextElement; return true; } // else traverse the list while (currentNode.nextElement != null) { // if a node whose next node has the value as data, is found, delete it from the list and return true if (currentNode.nextElement.data == value) { currentNode.nextElement = currentNode.nextElement.nextElement; return true; } currentNode = currentNode.nextElement; } //else node was not found, return false deleted = false; return deleted; } deleteAtTail() { // check for the case when linked list is empty if (this.isEmpty()) { return this; } //if linked list is not empty, get the pointer to first node let firstNode = this.head; //check for the corner case when linked list has only one element if (firstNode.nextElement == null) { this.deleteAtHead(); return this; } //otherwise traverse to reach second last node while (firstNode.nextElement.nextElement != null) { firstNode = firstNode.nextElement; } //since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node firstNode.nextElement = null; return this; } }
Code language: JavaScript (javascript)
"use strict"; module.exports = class Node { constructor(data) { this.data = data; this.nextElement = null; } }
Code language: JavaScript (javascript)

Vì các đỉnh của chúng ta được lưu trữ trong một mảng, chúng ta có thể truy cập vào  source danh sách được liên kết. Sau đó, chúng tôi gọi  delete hàm cho danh sách được liên kết. Độ phức tạp về thời gian cho giải pháp này là O (E) vì chúng ta có thể phải đi qua các cạnh E.

Bảng băm: Chuyển đổi Max-Heap thành Min-Heap

Tuyên bố vấn đề: Thực hiện chức năng  convertMax(maxHeap) chuyển đổi max-heap nhị phân thành min-heap nhị phân.  maxHeap phải là một mảng trong  maxHeap định dạng, tức là phần cha lớn hơn phần con của nó.

Đầu vào: a Max-Heap

maxHeap = [9,4,7,1,-2,6,5]

Đầu ra: trả về mảng đã chuyển đổi

result = [-2,1,5,9,4,6,7]

Để giải quyết vấn đề này, chúng ta phải tối thiểu hóa tất cả các nút cha. 

function minHeapify(heap, index) { var left = index * 2; var right = (index * 2) + 1; var smallest = index; if ((heap.length > left) && (heap[smallest] > heap[left])) { smallest = left } if ((heap.length > right) && (heap[smallest] > heap[right])) smallest = right if (smallest != index) { var tmp = heap[smallest] heap[smallest] = heap[index] heap[index] = tmp minHeapify(heap, smallest) } return heap; } function convertMax(maxHeap) { for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--) maxHeap = minHeapify(maxHeap, i) return maxHeap } var maxHeap = [9,4,7,1,-2,6,5] console.log(convertMax(maxHeap))
Code language: JavaScript (javascript)

Chúng tôi coi  maxHeap nó là một mảng thông thường và sắp xếp lại nó để thể hiện chính xác một min-heap. Bạn có thể thấy điều này được thực hiện trong đoạn mã trên. Sau  convertMax() đó, hàm khôi phục thuộc tính heap trên tất cả các nút từ nút cha thấp nhất bằng cách gọi  minHeapify() hàm. Liên quan đến độ phức tạp về thời gian, giải pháp này cần thời gian O(nlog(n))O(nlog (n)) .

Kết luận

Rõ ràng có rất nhiều thứ để học khi nói đến cấu trúc dữ liệu trong JavaScript. Thực hành thực hành là chìa khóa để thành công với các cuộc phỏng vấn viết mã. Điều quan trọng là phải vượt ra ngoài lý thuyết và áp dụng những khái niệm này vào các giải pháp trong thế giới thực.

Chúc các bạn học tập vui vẻ!

Cảm ơn bạn đã theo dõi bài viết!

Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.


Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.

TỔNG HỢP TÀI LIỆU HỌC LẬP TRÌNH CƠ BẢN CHO NGƯỜI MỚI BẮT ĐẦU

KHOÁ HỌC BOOTCAMP JAVA/JAVASCRIPT/PHP TRỞ THÀNH LẬP TRÌNH VIÊN TRONG 5-6 THÁNG

Leave a Reply

Your email address will not be published.