Data Structures & Algorithms - Part 01
Before we get into arrays, linked lists, or algorithms, let's start with a simple question: where does data live while a program is running? In this first article, we'll go from an ordinary desk to tiny memory slots, so a line like int[] arr = {1, 3, 5} becomes something you can picture not just syntax you have to remember.
Think of RAM as your desk: it holds the data a program is currently working with. An SSD or hard drive is more like a filing cabinet, keeping data for the long term.
Ordinary RAM loses its contents when power is lost. Unsaved changes may disappear, while a copy already saved to storage remains.
Data in memory is represented by bits: 0s and 1s. One byte contains 8 bits. In Java, an int holds 32 bits of data, equivalent to 4 bytes.
An address tells you where data is; a value tells you what is there. In a contiguous array model with equal-sized elements, an element’s address is calculated as: base address + index × element size.
“Random access” does not mean choosing something randomly. Given an index, a program can access an array element without reading every preceding element. In the standard algorithmic model, this takes O(1) time.
Consecutive addresses seen by a program do not necessarily correspond to adjacent locations in physical RAM, because programs typically use virtual addresses.
A character does not always fit in one byte. In Java, a char is a 2-byte UTF-16 code unit; a single character that a person sees may require multiple code units.
🌐 Languages: English · Tiếng Việt bên dưới
1. RAM is your desk, not your filing cabinet
Imagine preparing a presentation. You take a few documents out of a filing cabinet, open your notebook, and put what you need on your desk. The other documents stay in the cabinet; you don't need everything out at once.
Think of the computer the same way: the SSD or hard drive is the filing cabinet, RAM is the desk, and the CPU is the person doing the work. RAM, short for Random Access Memory, holds working data for quick access by the processor. [1]
Ordinary RAM does not retain its contents without power. Changes held only in RAM can be lost, while saved copies remain on storage. A recovered document doesn't mean RAM remembered it—the application may have saved a copy earlier. [1]
The picture in a diagram
Đang vẽ sơ đồ…
Xem mã sơ đồ
```mermaid
flowchart LR
S["SSD / HDD<br/>Filing cabinet"]
R["RAM<br/>Desk"]
C["CPU<br/>Person doing the work"]
S -->|"Load data"| R
R -->|"Read"| C
C -->|"Write results"| R
R -->|"Save through the application and OS"| S
```
A simplified model of the roles; caches, registers, and operating-system layers are omitted.
2. What is actually inside memory?
A real desk holds paper, books, and pens. Memory represents data as bits, each with a value of 0 or 1. Picture a tiny switch with just two states: off or on.
Put eight switches together and you have one byte: 1 byte = 8 bits. [2]
Spam checks run automatically. Some comments may be held for review.
Related posts
Loading related posts…
3
, and
5
can be written using the eight-bit patterns below. This illustrates the values in one byte;
it does not mean a Java
int
occupies one byte
.
Decimal number
Eight-bit binary
1
00000001
3
00000011
5
00000101
The two active positions are worth 4 and 1, so 00000101 = 4 + 1 = 5.
A quick note on capacity: By the standard definitions, 1 GB = 1,000,000,000 bytes, while 1 GiB = 1,073,741,824 bytes. Therefore, 8 GB = 8,000,000,000 bytes, not 10⁹ bytes. [2]
3. A value also needs a location
Now imagine a tray of small numbered compartments on your desk. Tell someone to “get the item in compartment 12,” and they know where to look without opening every compartment first.
We'll use that picture for memory: each slot in this model holds one byte and has an address. The address answers “where?” The value answers “what is there?”
For example, if a number occupies the four bytes at 1000, 1001, 1002, and 1003, its starting address is 1000. The addresses in this article are made-up numbers chosen to keep the arithmetic simple.
Technical note: Programs typically work with virtual addresses. A contiguous virtual address range need not be contiguous in physical RAM. We are using the program's address-space view, not a physical map of a RAM module. [3]
4. Putting [1, 3, 5] into memory
Now we can connect that picture to a familiar line of Java:
Code
int[] arr = {1, 3, 5};
In Java, an int is a 32-bit integer, equivalent to four bytes of data. [4] For our illustration, we'll place the three elements in a contiguous region and assume the first element starts at address 1000.
The value 1 uses the first four slots. The value 3 uses the next four. The value 5 uses the four after that. Their starting addresses are therefore 1000, 1004, and 1008, with no gaps between the elements.
Element
Value
Start address
Byte range
arr[0]
1
1000
1000–1003
arr[1]
3
1004
1004–1007
arr[2]
5
1008
1008–1011
Watch it happen
Each GIF slot is one byte. 01, 03, 05, and 00 are hexadecimal byte values. This illustration uses little-endian order, placing the least significant byte first. Dashes mark content not yet introduced in the animation; they do not represent uninitialized Java array elements.
Here is a still image of reading the third element:
Scope of the illustration:3 × 4 = 12 bytes counts only the three element values, not the total footprint of a Java array object. Metadata, alignment, and the reference variable are omitted; the illustration does not prescribe a layout for every JVM.
5. “Random access” does not mean picking at random
Back to the numbered tray: once you know the compartment, you go there. You don't have to open the first compartment and work your way along.
That's the idea behind direct access. In our model of an array with equal-sized, contiguous elements, the starting address, element index, and element size are enough to calculate where to read:
Code
address = baseAddress + index × elementSize
For arr[2], the calculation is:
Code
1000 + 2 × 4 = 1008
Đang vẽ sơ đồ…
Xem mã sơ đồ
```mermaid
flowchart TD
A["Read arr[2]"]
B["Base address: 1000"]
C["Offset: 2 × 4 = 8 bytes"]
D["Read address: 1008"]
E["Read 4 bytes and decode 5"]
A --> B --> C --> D --> E
```
This also gives zero-based indexing a practical meaning: the first element is zero bytes away from the start. arr[0] has an offset of 0 × 4; arr[1] has an offset of 1 × 4. Java indices run from 0 to length - 1. [5]
In this algorithmic model, calculating the address and reading one element costs O(1): a longer array does not require scanning more elements first. That does not promise identical elapsed time for every hardware access; it describes the amount of work at the algorithm level.
6. What about letters?
Data isn't limited to numbers. We can store text too, but one common shortcut is misleading: “every character takes one byte.” That works for ASCII letters such as A, B, and C encoded as ASCII or UTF-8, not for all characters. [6]
In Java, a char is 16 bits, or two bytes, and represents a UTF-16 code unit. [4] In the same illustrative layout, the elements below would therefore start two bytes apart, not one:
Code
char[] letters = {'A', 'B', 'C'};
Element
Value
Illustrative address
letters[0]
A
2000
letters[1]
B
2002
letters[2]
C
2004
A character as a reader sees it can require multiple code units. Ask “which data type and encoding are we using?” rather than assuming one letter equals one byte. [6]
7. Where do data structures fit in?
Having a desk doesn't mean everything on it is well organized. You might arrange documents in a row, stack them, or sort them into compartments. Each arrangement makes certain tasks easier.
A data structure organizes data around the operations we need, such as reading, searching, inserting, or deleting. So far, we've met one idea: put equal-sized elements next to each other so their positions can be calculated.
That leads naturally to another question: what happens when the row is full and you need to insert something in the middle? Do the other elements have to move?
That's where we'll pick up next: Arrays—why reading is quick, but inserting and deleting take a little more thought.
Start with the desk and the numbered compartments. The terminology can come with practice.
🇻🇳 Phiên bản tiếng Việt
1. RAM là bàn làm việc, không phải tủ hồ sơ
Giả sử bạn đang chuẩn bị một bài thuyết trình. Bạn lấy tài liệu trong tủ ra, mở sổ ghi chú rồi đặt những thứ cần dùng lên bàn. Tủ vẫn giữ các tài liệu khác; bạn không cần mang hết chúng ra cùng lúc.
Có thể hình dung máy tính theo cách tương tự: SSD hoặc ổ cứng là tủ hồ sơ, RAM là mặt bàn, còn CPU là người đang làm việc. RAM, viết tắt của Random Access Memory, giữ dữ liệu đang được sử dụng để bộ xử lý có thể truy cập nhanh. [1]
RAM thông thường không giữ được dữ liệu khi mất nguồn. Vì vậy, phần chỉnh sửa chỉ nằm trong RAM có thể bị mất; bản đã lưu trên ổ đĩa vẫn còn. Đừng nhầm chuyện ứng dụng khôi phục được tài liệu với chuyện RAM tự nhớ: ứng dụng có thể đã lưu một bản trước đó. [1]
Nhìn bằng sơ đồ
Đang vẽ sơ đồ…
Xem mã sơ đồ
```mermaid
flowchart LR
S["SSD / HDD<br/>Tủ hồ sơ"]
R["RAM<br/>Bàn làm việc"]
C["CPU<br/>Người xử lý"]
S -->|"Nạp dữ liệu"| R
R -->|"Đọc"| C
C -->|"Ghi kết quả"| R
R -->|"Lưu qua ứng dụng và hệ điều hành"| S
```
Mô hình đơn giản để phân biệt vai trò; sơ đồ bỏ qua bộ nhớ đệm, thanh ghi và các lớp xử lý của hệ điều hành.
2. Bên trong bộ nhớ có gì?
Trên bàn thật có giấy, sách và bút. Trong bộ nhớ, dữ liệu được biểu diễn bằng các bit, mỗi bit có giá trị 0 hoặc 1. Bạn có thể tưởng tượng một bit như công tắc nhỏ chỉ có hai trạng thái: tắt hoặc bật.
Gom tám công tắc lại, ta có một byte: 1 byte = 8 bit. [2]
Chẳng hạn, các số 1, 3, 5 có thể viết dưới dạng nhị phân tám bit như bảng dưới. Đây là ví dụ biểu diễn giá trị trong một byte, chưa phải kích thước của kiểu int trong Java.
Số thập phân
Biểu diễn nhị phân 8 bit
1
00000001
3
00000011
5
00000101
Ở hình trên, hai vị trí đang bật có giá trị 4 và 1, nên 00000101 = 4 + 1 = 5.
Một chút về dung lượng: Theo cách gọi chuẩn, 1 GB = 1.000.000.000 byte, còn 1 GiB = 1.073.741.824 byte. Vì thế, 8 GB = 8.000.000.000 byte, không phải 10⁹ byte. [2]
3. Biết giá trị chưa đủ, còn phải biết nó ở đâu
Giờ hãy tưởng tượng trên bàn có một khay gồm nhiều ngăn nhỏ, mỗi ngăn được đánh số. Bạn nói “lấy đồ trong ngăn 12” thì người khác biết phải tìm ở đâu, không cần mở từng ngăn từ đầu.
Ta dùng hình ảnh đó để hình dung bộ nhớ: mỗi ô trong mô hình này chứa một byte và có một địa chỉ. Địa chỉ trả lời câu hỏi “ở đâu?”, còn giá trị trả lời “ở đó có gì?”.
Ví dụ, nếu một số chiếm bốn byte ở các địa chỉ 1000, 1001, 1002, 1003, địa chỉ bắt đầu của số đó là 1000. Các con số địa chỉ trong bài chỉ được chọn để dễ tính.
Ghi chú kỹ thuật: Chương trình thường làm việc với địa chỉ ảo. Một vùng địa chỉ ảo liên tiếp không nhất thiết nằm liền nhau trong RAM vật lý. Bài này dùng góc nhìn địa chỉ của chương trình, không phải bản đồ vị trí trên thanh RAM. [3]
4. Đặt mảng [1, 3, 5] vào bộ nhớ
Đến đây, mình có thể nối câu chuyện với một dòng Java quen thuộc:
Code
int[] arr = {1, 3, 5};
Trong Java, int là số nguyên 32 bit, tương đương bốn byte dữ liệu. [4] Để minh họa, ta xếp ba phần tử thành một vùng liên tiếp và giả sử phần tử đầu tiên bắt đầu ở địa chỉ 1000.
Số 1 dùng bốn ô đầu. Số 3 dùng bốn ô kế tiếp. Số 5 dùng bốn ô ngay sau đó. Vì thế, các địa chỉ bắt đầu là 1000, 1004, 1008; giữa các phần tử không có khoảng trống.
Phần tử
Giá trị
Địa chỉ bắt đầu
Vùng byte
arr[0]
1
1000
1000–1003
arr[1]
3
1004
1004–1007
arr[2]
5
1008
1008–1011
Xem từng bước
Trong GIF, mỗi ô là một byte. 01, 03, 05, 00 là giá trị byte viết ở hệ 16; ví dụ chọn thứ tự little-endian, nghĩa là byte có trọng số thấp nằm trước. Dấu gạch ngang chỉ phần chưa được trình bày trong hoạt ảnh, không mô tả dữ liệu chưa khởi tạo trong Java.
Đây là ảnh tĩnh tại bước đọc phần tử thứ ba:
Phạm vi của hình:3 × 4 = 12 byte chỉ là dữ liệu của ba phần tử, không phải tổng bộ nhớ của một đối tượng mảng Java. Hình bỏ qua thông tin quản lý đối tượng, phần căn chỉnh và biến tham chiếu; cũng không quy định cách bố trí bộ nhớ cho mọi JVM.
5. “Random access” không có nghĩa là lấy đại
Quay lại khay có đánh số. Khi biết món đồ ở ngăn nào, bạn đến đúng ngăn đó. Bạn không bắt buộc mở ngăn đầu tiên rồi lần lượt đi tới ngăn cần lấy.
Đó là ý tưởng của truy cập trực tiếp. Với mô hình mảng có các phần tử cùng kích thước và nằm liền nhau, chỉ cần biết địa chỉ đầu, chỉ số phần tử và kích thước mỗi phần tử là tính được nơi cần đọc:
Code
địa chỉ = địa chỉ đầu + chỉ số × kích thước phần tử
Với arr[2], phép tính là:
Code
1000 + 2 × 4 = 1008
Đang vẽ sơ đồ…
Xem mã sơ đồ
```mermaid
flowchart TD
A["Đọc arr[2]"]
B["Địa chỉ đầu: 1000"]
C["Độ lệch: 2 × 4 = 8 byte"]
D["Địa chỉ cần đọc: 1008"]
E["Đọc 4 byte, giải mã được 5"]
A --> B --> C --> D --> E
```
Đây cũng là cách dễ hiểu để nhìn chỉ số bắt đầu từ 0: phần tử đầu tiên cách điểm bắt đầu không byte nào. arr[0] có độ lệch 0 × 4; arr[1] có độ lệch 1 × 4. Java dùng chỉ số từ 0 đến length - 1. [5]
Trong mô hình phân tích thuật toán này, tính địa chỉ rồi đọc một phần tử có chi phí O(1): không phải duyệt thêm phần tử chỉ vì mảng dài hơn. Điều đó không có nghĩa mọi lần đọc đều mất đúng một khoảng thời gian trên phần cứng thật; đây là cách đếm công việc ở mức thuật toán.
6. Còn chữ cái thì sao?
Dữ liệu không chỉ có số. Ta cũng có thể lưu văn bản, nhưng chỗ này có một câu dễ gây hiểu nhầm: “mỗi ký tự chiếm một byte.” Điều đó đúng với những chữ ASCII như A, B, C khi mã hóa bằng ASCII hoặc UTF-8, chứ không phải quy tắc chung cho mọi ký tự. [6]
Trong Java, một char là 16 bit, tức hai byte, và biểu diễn một đơn vị mã UTF-16. [4] Vì thế, trong mô hình tương tự, mảng dưới đây sẽ có địa chỉ bắt đầu các phần tử cách nhau hai byte, không phải một:
Code
char[] letters = {'A', 'B', 'C'};
Phần tử
Giá trị
Địa chỉ minh họa
letters[0]
A
2000
letters[1]
B
2002
letters[2]
C
2004
Một ký tự người dùng nhìn thấy còn có thể cần nhiều đơn vị mã. Vì vậy, hãy hỏi “đang dùng kiểu dữ liệu và cách mã hóa nào?” thay vì mặc định một chữ bằng một byte. [6]
7. Vậy cấu trúc dữ liệu liên quan gì?
Có một mặt bàn chưa có nghĩa là đồ trên bàn đã được sắp xếp hợp lý. Bạn có thể đặt tài liệu thành một hàng, xếp thành chồng, hoặc phân loại vào các ngăn. Mỗi cách sẽ tiện cho một việc khác nhau.
Cấu trúc dữ liệu là cách tổ chức dữ liệu để phục vụ những thao tác ta cần, chẳng hạn đọc, tìm kiếm, thêm hoặc xóa. Trong bài này, ta mới gặp một ý tưởng: đặt các phần tử cùng kích thước liền nhau để tính được vị trí của chúng.
Từ đó, câu hỏi tiếp theo xuất hiện rất tự nhiên: nếu cả hàng đã kín mà muốn chèn một phần tử vào giữa thì sao? Có phải dời các phần tử khác đi không?
Đó sẽ là chuyện của bài kế tiếp: Mảng — vì sao đọc nhanh, nhưng thêm và xóa lại cần suy nghĩ thêm?
Nhớ chiếc bàn và những ngăn có địa chỉ là đủ để bắt đầu. Không cần thuộc hết thuật ngữ trong lần đọc đầu tiên.
