Tôi bẽn lẽn

Anh nhẹ nhàng nói:

– Sinh viên bây giờ thiếu quá nhiều kĩ năng làm việc, em cần phải được đào tạo lại từ đầu. Ngày mai anh sẽ dậy cho em những kiến thức cơ bản về Cấu trúc dữ liệu và giải thuật. Đây là những kiến thức nền tảng mà bất kì ai cũng cần phải nắm vững khi làm trong ngành CNTT.

Ngay cả những tập đoàn lớn nhưng Amazon, hay Google khi phỏng vấn họ cũng hỏi em những câu hỏi về lĩnh vực này

Cấu trúc dữ liệu là cách để tổ chức data trong máy tính để có thể sử dụng một cách hiệu quả. Thuật toán, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước.

 

Em cứ hình dung, ngôn ngữ lập trình thì cũng như tiếng Việt hay tiếng Anh, biết thì nói chuyện được sơ sơ, nói và viết được các nội dung đơn giản. Cấu trúc dữ liệu thì như ngữ pháp, biết cách dùng rồi thì viết câu sẽ chuẩn hơn, ai cũng hiểu, không hiểu nhầm.

 

Còn giải thuật thì như là nội dung nói (hoặc viết) vậy, trong đó có cách tổ chức bài nói (hoặc bài viết), nói gì, ý trước ý sau ra sao, phân tích, lập luận thế nào…

 

Anh sẽ giảng giải cho em những kiến thức về Cấu trúc dữ liệu và thuật toán từ đơn giản đến nâng cao. Từ dữ liệu stack, tree cho tới lý thuyết đồ thị, kĩ thuật duyệt cây nhị phân, duyệt đồ thị…

Cấu trúc dữ liệu thì bao gồm cấu trúc đơn giản và nâng cao như sau:

Array

 

Mảng có thể lưu giữ một số phần tử cố định và các phần tử này nền có cùng kiểu. Hầu hết các cấu trúc dữ liệu đều sử dụng mảng để triển khai giải thuật.

 

Hãy tưởng tượng có rất nhiều chàng trai yêu em, mỗi người được lưu vào trong 1 mảng. Mỗi chàng trai là 1 phần tử của mảng, được đánh index theo thứ tự từ 0 để nhận dạng và được lưu liên tục trong RAM như hình trên

 

Em có thể dễ dàng tìm kiếm các chàng trai trong mảng, thêm, sửa, và loại đi những chàng trai mà em không thích bằng đoạn code như sau

public class TestArray {

  public static void main(String[] args) {
      // Declare array
     string[] myLoveList = {'Minh','Nam', 'Nguyen', 'Hung'};

     // Print all the array elements
     for (int i = 0; i < myLoveList.length; i++) {
        System.out.println(myLoveList[i] + " ");
     }
    
     // Choose a lover : Nam
     System.out.println(myLoveList[1] + " ");
  }
}

Ưu điểm của mảng

Ưu điểm của mảng là tốc độ truy cập nhanh và có thể truy cập đến các vị trí ngẫu nhiên.

Nhược điểm của mảng

Kích thước của mảng luôn phải cố định và phải dc khai báo trước khi chạy chương trình. Hãy tưởng tượng em tạo một mảng gồm 4 người thích em. Điều gì xảy ra nều em muốn có 10, 20 người thích em sau này.

 

Thực tế vùng nhớ chương trình là ko thể dự báo trước, cũng như ko thể đoán trước có bao nhiêu người yêu em. Khai báo mảng quá lớn hay quá nhỏ đếu dẫn tới thiếu hoặc dư thừa bộ nhớ.

 

Một điều quan trọng nữa có thể em chưa biết. Các byte vùng nhớ cấp phát mảng được sắp xếp liên tục. Nếu như vùng nhớ bị phân mảnh giống như phân mảnh đĩa thì chương trình sẽ báo lỗi không đủ vùng nhớ liên tục.

 

Ngay cả việc chèn, hay xóa phần tử ở vị trí N trong mảng cũng sẽ ảnh hưởng performance, khi các toàn bộ phần tử từ N trở đi phải dịch đi.

 

Em muốn thêm Linh vào vị trí thứ 3 thì Minh và Hoang phải lùi lại làm người đến sau. Nếu người yêu em có hàng triệu thì em sẽ thấy performance ảnh hưởng thế nào chứ.

Vì thế có một loại cấu trúc dữ liệu mới được sử dụng đó là: LinkedList

LinkedList

Em hãy tưởng tượng những chàng trai của em sẽ xếp thành hàng dài để đợi em, tay người này nắm lấy áo của người kia. Em sẽ có dữ liệu LinkedList

Có 3 loại LinkedList

• Linked List Basic
• Doubly Linked List
• Circular Linked List

Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi.

Đây là hình ảnh mô tả một danh sách liên kết.

• Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
• Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next.
• First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First

Đây là code sample của LinkedList. Có 3 chàng trai Nam, Minh, Trung cùng xếp hàng chờ đợi em .Mỗi node đại diện cho 1 chàng trai, tay chàng trai này nắm lấy áo của người trước đó. Trung là người cuối hàng, sẽ không có ai nắm lấy áo bạn ấy (Link là null)

// A simple Java program to introduce a linked list
class LinkedList
{
    Node head;  // head of list

    /* Linked list Node.  This inner class is made static so that
       main() can access it */
    static class Node {
       String data;
        Node next;
        Node(String d)  { data = d;  next=null; } // Constructor
    }

    /* method to create a simple linked list with 3 nodes*/
    public static void main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList llist = new LinkedList();

        llist.head  = new Node('Nam');
        Node second = new Node('Minh');
        Node third  = new Node('Trung');

        /* Three nodes have been allocated  dynamically.
          We have refernces to these three blocks as first, 
          second and third

          llist.head        second              third
             |                |                  |
             |                |                  |
         +----+------+     +----+------+     +----+------+
         | Nam  | null |   | Minh  | null |  | Trung | null |
         +----+------+     +----+------+     +----+------+ */

        llist.head.next = second; // Link first node with the second node

        /*  Now next of first Node refers to second.  So they
            both are linked.

         llist.head        second              third
            |                |                  |
            |                |                  |
        +----+------+     +----+------+     +----+------+
        | Nam   |  o----->| Minh  | null | |  Trung | null |
        +----+------+     +----+------+     +----+------+ */

        second.next = third; // Link second node with the third node

        /*  Now next of second Node refers to third.  So all three
            nodes are linked.

         llist.head        second              third
            |                |                  |
            |                |                  |
        +----+------+     +----+------+     +----+------+
        | Nam    |  o---->| Minh   |  o--- ->|  Trung | null |
        +----+------+     +----+------+     +----+------+ */
    }
}

 

Tuy nhiên danh sách liên kết đơn lại có một số ưu nhược điểm mà em cần chú ý

Ưu điểm

Em có thể lưu những chàng trai đang yêu em một cách dễ dàng, thêm hoặc xóa các chàng trai trong danh sách mà không cần phải cấp phát hoặc tổ chức lại trật tự của mảng. Hơn nữa bộ nhớ được cấp phát động nên em sẽ tối ưu hóa memory hơn là khai báo kiểu mảng tĩnh như ở trên

Nhược điểm

Hãy tưởng tượng 3 chàng trai Nam, Minh, Trung đợi em những em muốn chọn chàng trai cuối cùng, hoặc thêm một người em thích vào danh sách, em đều phải duyệt từ đầu vì một danh sách liên kết đơn không cho phép truy cập ngẫu nhiên dữ liệu.