Chương 10: Collection

Tham khảo tài liệu chương 10: collection,Linked list là cấu trúc gồm các node liên kết với nhau thông qua các mối liên kết, Node cuối linked list được đặt là null để đánh dấu kết thúc danh sách.
Nội dung trích xuất từ tài liệu:
Chương 10: Collection Chương 10: Collection Collection GVLT: Tr n Anh Dũng 1 N i dungC u trúc d li u trong Java Array LinkedList Stack và QueueCollections Framework Danh sách (List) T p h p (Set) B ng ánh x (Map) 2 Linked ListLinked list là c u trúc g m các node liên k t v i nhauthông qua các m i liên k t. Node cu i linked list ñư cñ t là null ñ ñánh d u k t thúc danh sách.Linked list giúp ti t ki m b nh so v i m ng trong cácbài toán x lý danh sách.Khi chèn/xoá m t node trên linked list, không ph idãn/d n các ph n t như trên m ng.Vi c truy nh p trên linked list luôn ph i tu n t . 3 Linked ListTh hi n Node thông qua l p t tham chi u (self-referential class)M t linked list ñư c qu n lý b i tham chi u t i node ñ uvà node cu i (firstNode & lastNode).class Node { private int data; private Node nextNode; // constructors and methods...} 15 10 4 Cài ñ t Linked List// Dinh nghia mot node trong linked listclass ListNode { int data; ListNode nextNode; ListNode(int value){ this(value, null); } ListNode(int value, ListNode node){ data = value; nextNode = node; } int getData(){ return data; } ListNode getNext() { return nextNode; }} 5 Cài ñ t Linked List// Dinh nghia lop LinkedListpublic class LinkedList { private ListNode firstNode; private ListNode lastNode; public LinkedList(){ firstNode = lastNode = null; } public void insertAtFront(int insertItem){ if ( isEmpty()) firstNode=lastNode=new ListNode(insertItem); else firstNode=new ListNode(insertItem, firstNode); } 6 Cài ñ t Linked Listpublic void insertAtBack( int insertItem ){ if ( isEmpty() ) firstNode = lastNode = new ListNode( insertItem ); else 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;} 7 Cài ñ t Linked Listpublic 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; current.nextNode = null; } } return removeItem;} 8 Cài ñ t Linked List public boolean isEmpty() { return (firstNode == null); } public void print() { ListNode node = firstNode; while (node != null) { System.out.print(node.data + ); node = node.nextNode; } System.out.println( ); }} 9 StackStack 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 ph n t : Luôn l y ra t ñ nh Stack (pop)Ví d : Stack s = new Stack(); s.push(10); s.push(25); while (!s.isEmpty()) System.out.print(s.pop() + ); 10 Gi i thi uCollection là ñ i tư ng có kh năng ch a các ñ i tư ngkhác.Các thao tác thông thư ng trên collection: Thêm/Xoá ñ i tư ng vào/kh i collection Ki m tra m t ñ i tư ng có trong collection không L y m t ñ i tư ng t collection Duy t các ñ i tư ng trong collection Xoá toàn b collection 11 Collections FrameworkCác collection ñ u tiên c a Java: M ng Vector: M ng ñ ng Hastable: B ng bămCollections Framework (t Java 1.2) Là m t ki n trúc h p nh t ñ bi u di n và thao tác trên các collection. Giúp cho vi c x lý các collection ñ c l p v i bi u di n chi ti t bên trong c a chúng. ...