1
Lập trình Java cơ bản
Cao Đức Thông   Trần Minh Tuấn­
,  
2
Bài 8. Collections
•
Cấu trúc dữ liệu trong Java
•
Linked List
•
Stack và Queue
•
Tree
•
Collections Framework
•
Danh sách (List)
•
Tập hợp (Set)
•
Bảng ánh xạ (Map)
•
Bài tập
3
Cấu trúc dữ liệu
•
Cấu trúc dữ liệu là cách tổ chức dữ liệu để giải 
quyết vấn đề.
•
Một số cấu trúc dữ liệu phổ biến:

{
private int data;
private Node nextNode;
// constructors and methods ...
}
15 10
6
Linked List
•
Một linked list được quản lý bởi tham chiếu tới 
node đầu và node cuối.
H D Q
firstNode lastNode
...
7
Cài đặt Linked List
// Dinh nghia mot node trong linked list         
class ListNode 
{
     int data;
     ListNode nextNode;
     ListNode(int value) 
     {
this(value, null); 
     }
     ListNode(int value, ListNode node)
     {
data = value;    
nextNode = node; 
     }

           lastNode = lastNode.nextNode = new ListNode( insertItem );
    }
    public int removeFromFront()
    {
        int removeItem =  1;­
        if ( ! isEmpty() ) {
 removeItem = firstNode.data;  
 if ( firstNode == lastNode )
     firstNode = lastNode = null;
            else
     firstNode = firstNode.nextNode;
        }
        return removeItem;  
    }
10
Cài đặt Linked List
     public int removeFromBack()
     {
int removeItem =  1;­
if ( ! isEmpty() )
{
           removeItem = lastNode.data;  
      if ( firstNode == lastNode )
firstNode = lastNode = null;
      else
      {
ListNode current = firstNode;
while ( current.nextNode != lastNode )
       current = current.nextNode;
lastNode = current;

firstNode
12
new ListNode
(b)
13
Mô tả insertAtBack
12 7 11
firstNode lastNode
(a)
5
new ListNode
12 11
firstNode lastNode
(b)
5
new ListNode
7
14
Mô tả removeFromFront
firstNode lastNode
(a)
11
firstNode lastNode
(b)
removeItem
12
12
7
7 5
5

list.removeFromFront();
list.removeFromBack();
          list.print();
      }
}  
17
Stack
•
Stack là một cấu trúc theo kiểu LIFO (Last In 
First Out), phần tử vào sau cùng sẽ được lấy ra 
trước.
•
Hai thao tác cơ bản trên Stack
•
Chèn phần tử: Luôn chèn vào đỉnh Stack (push)
•
Lấy ra phần tử: Luôn lấy ra từ đỉnh Stack (pop)
18
Cài đặt Stack
public class Stack
{
      private LinkedList stackList;
      public Stack()   
      { 
           stackList = new LinkedList(); 
      }
      public void push( int value )
      { 
          stackList.insertAtFront( value ); 
      }

Chèn phần tử: Luôn chèn vào cuối hàng đợi 
(enqueue)
•
Lấy ra phần tử: Lấy ra từ đầu hàng đợi (dequeue)
21
Cài đặt Queue
public class Queue
{
      private LinkedList queueList;
      public Queue() 
      { 
           queueList = new LinkedList(); 
      }
      public void enqueue( int value )
      { 
           queueList.insertAtBack( value ); 
      }
      public int dequeue()  { return queueList.removeFromFront();  }
      public boolean isEmpty() { return queueList.isEmpty(); }
      public void print() { queueList.print(); }
}
22
Sử dụng Queue
public class QueueTest
{
      public static void main(String[] args) 
      {
Queue queue = new Queue();
queue.enqueue(5);
queue.enqueue(7);

nút cha.
•
Duyệt cây nhị phân
•
Inorder traversal
•
Preorder traversal
•
Postorder traversal
25
Binary Search Tree
•
Ví dụ về Binary Search Tree
47
25 77
11 43 65 93
687 17 3144
Cây con trái Cây con phải