10 cấu trúc dữ liệu phổ biến được giải thích bằng video + bài tập

Các lập trình viên của Bad Bad lo lắng về mã. Các lập trình viên giỏi lo lắng về cấu trúc dữ liệu và các mối quan hệ của họ. - - Linus Torvalds, người tạo ra Linux
** Cập nhật ** Khóa học video của tôi về Thuật toán hiện đã có! Kiểm tra các thuật toán trong chuyển động từ ấn phẩm Manning. Nhận 39% cho khóa học của tôi bằng cách sử dụng mã ‘39carnes Kiểu! Hoặc bạn có thể nhận được 50% cho khóa học Deep Learning in Motion của tôi với mã ‘vlcarnes2 triệt.

Cấu trúc dữ liệu là một phần quan trọng của phát triển phần mềm và là một trong những chủ đề phổ biến nhất cho các câu hỏi phỏng vấn công việc của nhà phát triển.

Tin tốt là về cơ bản họ chỉ là các định dạng chuyên biệt để tổ chức và lưu trữ dữ liệu.

Tôi sẽ dạy cho bạn 10 cấu trúc dữ liệu phổ biến nhất - ngay trong bài viết ngắn này.

Tôi đã nhúng các video mà tôi đã tạo cho mỗi cấu trúc dữ liệu này. Tôi cũng đã liên kết với các ví dụ mã cho từng ví dụ, cho biết cách triển khai các ví dụ này trong JavaScript.

Và để cung cấp cho bạn một số thực hành, tôi đã liên kết với các thách thức từ chương trình giảng dạy freeCodeCamp.

Lưu ý rằng một số cấu trúc dữ liệu này bao gồm độ phức tạp thời gian trong ký hiệu Big O. Điều này được bao gồm cho tất cả chúng vì sự phức tạp về thời gian đôi khi dựa trên cách thức mà nó thực hiện. Nếu bạn muốn tìm hiểu thêm về Ký hiệu Big O, hãy xem bài viết của tôi về nó hoặc video này của Briana Marie.

Cũng lưu ý rằng mặc dù tôi chỉ ra cách triển khai các cấu trúc dữ liệu này trong JavaScript, nhưng đối với hầu hết chúng, bạn sẽ không bao giờ cần phải tự thực hiện chúng, trừ khi bạn đang sử dụng ngôn ngữ cấp thấp như C.

JavaScript (giống như hầu hết các ngôn ngữ cấp cao) có triển khai tích hợp nhiều cấu trúc dữ liệu này.

Tuy nhiên, biết cách triển khai các cấu trúc dữ liệu này sẽ mang lại cho bạn một lợi thế lớn trong tìm kiếm công việc dành cho nhà phát triển của bạn và có thể hữu ích khi bạn đang cố gắng viết mã hiệu suất cao.

Danh sách liên kết

Một danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản nhất. Nó thường được so sánh với một mảng vì nhiều cấu trúc dữ liệu khác có thể được thực hiện với một mảng hoặc danh sách được liên kết. Họ đều có ưu điểm và nhược điểm.

Đại diện danh sách liên kết

Một danh sách được liên kết bao gồm một nhóm các nút cùng thể hiện một chuỗi. Mỗi nút chứa hai thứ: dữ liệu thực tế đang được lưu trữ (về cơ bản có thể là bất kỳ loại dữ liệu nào) và một con trỏ (hoặc liên kết) đến nút tiếp theo trong chuỗi. Ngoài ra còn có các danh sách được liên kết đôi khi mỗi nút có một con trỏ tới cả mục tiếp theo và mục trước trong danh sách.

Các thao tác cơ bản nhất trong danh sách được liên kết là thêm một mục vào danh sách, xóa một mục khỏi danh sách và tìm kiếm danh sách cho một mục.

Xem mã cho danh sách được liên kết trong JavaScript tại đây.

Danh sách thời gian liên kết phức tạp
╔═══════════╦═════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬═════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (n) O (n)
Chèn O (1) O (1)
Xóa ║ O (1) O (1)
╚═══════════╩═════════╩════════════╝

những thách thức freeCodeCamp

  • Làm việc với các nút trong danh sách liên kết
  • Tạo một lớp danh sách liên kết
  • Xóa các thành phần khỏi danh sách liên kết
  • Tìm kiếm trong Danh sách liên kết
  • Xóa các thành phần khỏi danh sách được liên kết theo chỉ mục
  • Thêm các yếu tố tại một chỉ mục cụ thể trong danh sách liên kết
  • Tạo một danh sách liên kết đôi
  • Đảo ngược danh sách liên kết đôi

Ngăn xếp

Ngăn xếp là cấu trúc dữ liệu cơ bản trong đó bạn chỉ có thể chèn hoặc xóa các mục ở đầu ngăn xếp. Nó là loại tương tự như một chồng sách. Nếu bạn muốn xem một cuốn sách ở giữa chồng bạn phải lấy tất cả những cuốn sách phía trên nó ra trước.

Ngăn xếp được coi là LIFO (Last In First Out) - có nghĩa là mục cuối cùng bạn đặt trong ngăn xếp là mục đầu tiên ra khỏi ngăn xếp

Đại diện ngăn xếp

Có ba thao tác chính có thể được thực hiện trên ngăn xếp: chèn một mục vào ngăn xếp (được gọi là 'đẩy'), xóa một mục khỏi ngăn xếp (được gọi là 'pop') và hiển thị nội dung của ngăn xếp (đôi khi được gọi là 'pip ').

Xem mã cho một ngăn xếp trong JavaScript ở đây.

Độ phức tạp thời gian
╔═══════════╦═════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬═════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (n) O (n)
Chèn O (1) O (1)
Xóa ║ O (1) O (1)
╚═══════════╩═════════╩════════════╝

những thách thức freeCodeCamp

  • Tìm hiểu cách hoạt động của Stack
  • Tạo một lớp ngăn xếp

Hàng đợi

Bạn có thể nghĩ về một hàng đợi như một dòng người tại một cửa hàng tạp hóa. Người đầu tiên trong hàng là người đầu tiên được phục vụ. Giống như một hàng đợi.

Đại diện xếp hàng

Một hàng đợi được coi là FIFO (First In First Out) để thể hiện cách nó truy cập dữ liệu. Điều này có nghĩa là một khi một phần tử mới được thêm vào, tất cả các phần tử đã được thêm vào trước đó phải được loại bỏ trước khi phần tử mới có thể được loại bỏ.

Một hàng đợi chỉ có hai thao tác chính: enqueue và dequeue. Enqueue có nghĩa là chèn một mục vào phía sau hàng đợi và dequeue có nghĩa là loại bỏ mục trước.

Xem mã cho một hàng đợi trong JavaScript ở đây.

Độ phức tạp thời gian xếp hàng
╔═══════════╦═════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬═════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (n) O (n)
Chèn O (1) O (1)
Xóa ║ O (1) O (1)
╚═══════════╩═════════╩════════════╝

những thách thức freeCodeCamp

  • Tạo một lớp xếp hàng
  • Tạo một lớp hàng đợi ưu tiên
  • Tạo một hàng đợi tròn

Bộ

Đặt đại diện

Cấu trúc dữ liệu được thiết lập lưu trữ các giá trị mà không có bất kỳ thứ tự cụ thể nào và không có giá trị lặp lại. Bên cạnh việc có thể thêm và xóa các phần tử vào một tập hợp, có một vài hàm tập hợp quan trọng khác hoạt động với hai bộ cùng một lúc.

  • Liên minh - Điều này kết hợp tất cả các mục từ hai bộ khác nhau và trả về đây là một bộ mới (không có bản sao).
  • Giao lộ - Cho hai bộ, hàm này trả về một bộ khác có tất cả các mục là một phần của cả hai bộ.
  • Sự khác biệt - Điều này trả về một danh sách các mục nằm trong một bộ nhưng KHÔNG ở một bộ khác.
  • Tập hợp con - Điều này trả về giá trị boolean cho biết nếu tất cả các phần tử trong một bộ được bao gồm trong một bộ khác.

Xem mã để triển khai một bộ trong JavaScript tại đây.

những thách thức freeCodeCamp

  • Tạo một lớp tập hợp
  • Xóa khỏi bộ
  • Kích thước của bộ
  • Thực hiện một liên minh trên hai bộ
  • Thực hiện giao lộ trên hai bộ dữ liệu
  • Thực hiện sự khác biệt trên hai bộ dữ liệu
  • Thực hiện kiểm tra tập hợp con trên hai bộ dữ liệu
  • Tạo và thêm vào bộ trong ES6
  • Xóa các mục khỏi một bộ trong ES6
  • Sử dụng .has và .size trên Bộ ES6
  • Sử dụng lây lan và ghi chú cho tích hợp ES5 Set ()

Bản đồ

Bản đồ là cấu trúc dữ liệu lưu trữ dữ liệu theo cặp khóa / giá trị trong đó mỗi khóa là duy nhất. Một bản đồ đôi khi được gọi là một mảng kết hợp hoặc từ điển. Nó thường được sử dụng để tra cứu dữ liệu nhanh chóng. Bản đồ cho phép những điều sau đây:

Đại diện bản đồ
  • việc thêm một cặp vào bộ sưu tập
  • loại bỏ một cặp khỏi bộ sưu tập
  • sửa đổi của một cặp hiện có
  • tra cứu một giá trị liên quan đến một khóa cụ thể

Xem mã để triển khai bản đồ trong JavaScript tại đây.

những thách thức freeCodeCamp

  • Tạo cấu trúc dữ liệu bản đồ
  • Tạo Bản đồ JavaScript ES6

Bảng băm

Bảng băm và biểu diễn hàm băm

Bảng băm là cấu trúc dữ liệu bản đồ chứa các cặp khóa / giá trị. Nó sử dụng hàm băm để tính toán một chỉ mục thành một mảng các nhóm hoặc vị trí, từ đó có thể tìm thấy giá trị mong muốn.

Hàm băm thường lấy một chuỗi làm đầu vào và nó xuất ra một giá trị số. Hàm băm phải luôn luôn cung cấp cùng một số đầu ra cho cùng một đầu vào. Khi hai đầu vào băm đến cùng một đầu ra số, đây được gọi là xung đột. Mục tiêu là có ít va chạm.

Vì vậy, khi bạn nhập cặp khóa / giá trị vào bảng băm, khóa sẽ được chạy qua hàm băm và biến thành số. Giá trị số này sau đó được sử dụng làm khóa thực tế mà giá trị được lưu trữ theo. Khi bạn cố gắng truy cập lại cùng một khóa, hàm băm sẽ xử lý khóa và trả về cùng một kết quả số. Số này sau đó sẽ được sử dụng để tra cứu giá trị liên quan. Điều này cung cấp trung bình thời gian tra cứu O (1) rất hiệu quả.

Xem mã cho một bảng băm ở đây.

Độ phức tạp của bảng băm
╔═══════════╦═════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬═════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (1) O (n)
Chèn O (1) O (n)
Xóa ║ O (1) O (n)
╚═══════════╩═════════╩════════════╝

những thách thức freeCodeCamp

  • Tạo bảng băm

Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân

Cây là một cấu trúc dữ liệu bao gồm các nút Nó có các đặc điểm sau:

  1. Mỗi cây có một nút gốc (ở trên cùng).
  2. Nút gốc có 0 hoặc nhiều nút con.
  3. Mỗi nút con có 0 hoặc nhiều nút con, v.v.

Cây tìm kiếm nhị phân thêm hai đặc điểm sau:

  1. Mỗi nút có tối đa hai con.
  2. Đối với mỗi nút, con cháu bên trái của nó nhỏ hơn nút hiện tại, ít hơn con cháu bên phải.

Cây tìm kiếm nhị phân cho phép tra cứu nhanh, bổ sung và loại bỏ các mục. Cách chúng được thiết lập có nghĩa là, trung bình, mỗi phép so sánh cho phép các thao tác bỏ qua khoảng một nửa cây, do đó, mỗi lần tra cứu, chèn hoặc xóa sẽ mất thời gian tỷ lệ với logarit của số lượng vật phẩm được lưu trữ trong cây.

Xem mã cho cây tìm kiếm nhị phân trong JavaScript tại đây.

Độ phức tạp thời gian tìm kiếm nhị phân
╔═══════════╦══════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬══════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (log n) O (n)
Chèn O (log n) O (n)
Xóa ║ O (log n) O (n)
╚═══════════╩══════════╩════════════╝

những thách thức freeCodeCamp

  • Tìm giá trị tối thiểu và tối đa trong cây tìm kiếm nhị phân
  • Thêm một yếu tố mới vào cây tìm kiếm nhị phân
  • Kiểm tra xem một phần tử có trong cây tìm kiếm nhị phân không
  • Tìm chiều cao tối thiểu và tối đa của cây tìm kiếm nhị phân
  • Sử dụng tìm kiếm sâu đầu tiên trong cây tìm kiếm nhị phân
  • Sử dụng Tìm kiếm đầu tiên theo chiều rộng trong Cây tìm kiếm nhị phân
  • Xóa một nút lá trong cây tìm kiếm nhị phân
  • Xóa một nút với một con trong cây tìm kiếm nhị phân
  • Xóa một nút có hai con trong cây tìm kiếm nhị phân
  • Đảo ngược cây nhị phân

Trie

Trie (phát âm ‘thử,), hay cây tiền tố, là một loại cây tìm kiếm. Một trie lưu trữ dữ liệu theo các bước trong đó mỗi bước là một nút trong trie. Các thử nghiệm thường được sử dụng để lưu trữ các từ để tra cứu nhanh, chẳng hạn như tính năng tự động hoàn thành từ.

Đại diện Trie

Mỗi nút trong bộ ba ngôn ngữ chứa một chữ cái của một từ. Bạn theo các nhánh của một trie để đánh vần một từ, một chữ cái tại một thời điểm. Các bước bắt đầu phân nhánh khi thứ tự của các chữ cái phân kỳ từ các từ khác trong trie hoặc khi một từ kết thúc. Mỗi nút chứa một chữ cái (dữ liệu) và boolean cho biết nút đó có phải là nút cuối cùng trong một từ hay không.

Nhìn vào hình ảnh và bạn có thể tạo thành từ. Luôn luôn bắt đầu tại nút gốc ở trên cùng và làm việc xuống. Trie hiển thị ở đây có chứa từ bóng, dơi, búp bê, làm, dork, ký túc xá, gửi, ý nghĩa.

Xem mã cho một trie trong JavaScript ở đây.

những thách thức freeCodeCamp

  • Tạo cây tìm kiếm Trie

Heap nhị phân

Một đống nhị phân là một loại cấu trúc dữ liệu cây. Mỗi nút có nhiều nhất là hai con. Ngoài ra, nó là một cây hoàn chỉnh. Điều này có nghĩa là tất cả các cấp được lấp đầy hoàn toàn cho đến cấp cuối cùng và cấp cuối cùng được điền từ trái sang phải.

Biểu diễn heap tối thiểu và tối đa

Một đống nhị phân có thể là một đống tối thiểu hoặc một đống tối đa. Trong một đống tối đa, các khóa của các nút cha luôn lớn hơn hoặc bằng với các nút của con cái. Trong một đống tối thiểu, các khóa của các nút cha mẹ nhỏ hơn hoặc bằng với các nút của con cái.

Thứ tự giữa các cấp là quan trọng nhưng thứ tự của các nút trên cùng cấp không quan trọng. Trong ảnh, bạn có thể thấy rằng cấp thứ ba của heap tối thiểu có các giá trị 10, 6 và 12. Những số đó không theo thứ tự.

Xem mã cho một đống trong JavaScript ở đây.

Phức tạp thời gian heap nhị phân
╔═══════════╦══════════╦════════════╗
Thuật toán ║ Trung bình Case Trường hợp xấu nhất
╠═══════════╬══════════╬════════════╣
Không gian O (n) O (n)
Tìm kiếm ║ O (n) O (n)
Chèn O (1) O (log n)
Xóa O (log n) O (log n)
Peek O (1) O (1)
╚═══════════╩══════════╩════════════╝

những thách thức freeCodeCamp

  • Chèn một phần tử vào một đống tối đa
  • Xóa phần tử khỏi Heap tối đa
  • Thực hiện Sắp xếp Heap với Heap tối thiểu

Đồ thị

Đồ thị là tập hợp các nút (còn được gọi là đỉnh) và các kết nối (được gọi là các cạnh) giữa chúng. Đồ thị còn được gọi là mạng.

Một ví dụ về đồ thị là một mạng xã hội. Các nút là người và các cạnh là tình bạn.

Có hai loại biểu đồ chính: có hướng và không có hướng. Đồ thị vô hướng là đồ thị không có bất kỳ hướng nào trên các cạnh giữa các nút. Các đồ thị có hướng, ngược lại, là các đồ thị có hướng ở các cạnh của nó.

Hai cách phổ biến để biểu diễn đồ thị là danh sách kề và ma trận kề.

Biểu đồ ma trận phụ trợ

Một danh sách kề có thể được biểu diễn dưới dạng một danh sách trong đó phía bên trái là nút và bên phải liệt kê tất cả các nút khác mà nó kết nối với nó.

Ma trận kề là một lưới các số, trong đó mỗi hàng hoặc cột biểu thị một nút khác nhau trong biểu đồ. Tại giao điểm của một hàng và một cột là một số chỉ ra mối quan hệ. Zeros có nghĩa là không có cạnh hoặc mối quan hệ. Những người có nghĩa là có một mối quan hệ. Các số cao hơn một có thể được sử dụng để hiển thị các trọng lượng khác nhau.

Các thuật toán truyền tải là các thuật toán để duyệt hoặc truy cập các nút trong biểu đồ. Các loại thuật toán truyền tải chính là tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu. Một trong những cách sử dụng là xác định các nút gần với nút gốc như thế nào. Xem cách triển khai tìm kiếm theo chiều rộng đầu tiên trong JavaScript trong video bên dưới.

Xem mã để tìm kiếm theo chiều rộng đầu tiên trên biểu đồ ma trận kề trong JavaScript.

Độ phức tạp thời gian của danh sách (đồ thị)
╔═══════════════╦════════════╗
Thuật toán Thời gian
╠═══════════════╬════════════╣
Lưu trữ ║ O (| V | + | E |)
║ Thêm Vertex ║ O (1)
║ Thêm cạnh ║ O (1)
Xóa Vertex O (| V | + | E |)
Xóa cạnh ║ O (| E |)
Truy vấn ║ O (| V |)
╚═══════════════╩════════════╝

những thách thức freeCodeCamp

  • Danh sách điều chỉnh
  • Ma trận kề
  • Ma trận tỷ lệ mắc
  • Bề rộng-Tìm kiếm đầu tiên
  • Độ sâu tìm kiếm đầu tiên

Hơn

Cuốn sách Thuật toán Grokking là cuốn sách hay nhất về chủ đề này nếu bạn chưa quen với các cấu trúc / thuật toán dữ liệu và don sắt có nền tảng khoa học máy tính. Nó sử dụng các giải thích dễ hiểu và các hình minh họa vẽ tay vui nhộn (của tác giả là nhà phát triển chính tại Etsy) để giải thích một số cấu trúc dữ liệu được nêu trong bài viết này.

Hoặc bạn có thể xem khóa học video của tôi dựa trên cuốn sách đó: Thuật toán chuyển động từ ấn phẩm Manning. Nhận 39% cho khóa học của tôi bằng cách sử dụng mã ‘39carnes Kiểu!