Lập trình Java cơ bản- Bài 8 (Collections)

Java (đọc như "Gia-va") là một ngôn ngữ lập trình dạng lập trình hướng đối tượng (OOP). Khác với phần lớn ngôn ngữ lập trình thông thường, thay vì biên dịch mã nguồn thành mã máy hoặc thông dịch mã nguồn khi chạy, Java được thiết kế để biên dịch mã nguồn thành bytecode, bytecode sau đó sẽ được môi trường thực thi (runtime environment) chạy. Bằng cách này, Java thường chạy chậm hơn những ngôn ngữ lập trình thông dịch khác như C++, Python, Perl, PHP, C#...Cú pháp Java được vay mượn nhiều từ C & C++ nhưng có...
Nội dung trích xuất từ tài liệu:
Lập trình Java cơ bản- Bài 8 (Collections)LậptrìnhJavacơbản CaoĐứcThôngTrầnMinhTuấn cdthong@ifi.edu.vn,tmtuan@ifi.edu.vn 1Bài8.Collections• CấutrúcdữliệutrongJava • LinkedList • StackvàQueue • Tree• CollectionsFramework • Danhsách(List) • Tậphợp(Set) • Bảngánhxạ(Map)• Bàitập 2Cấutrúcdữliệu• Cấutrúcdữliệulàcáchtổchứcdữliệuđểgiải quyếtvấnđề.• Mộtsốcấutrúcdữliệuphổbiến: • Mảng(Array) • Danhsáchliênkết(LinkedList) • Ngănxếp(Stack) • Hàngđợi(Queue) • Cây(Tree) 3LinkedList• Linkedlistlàcấutrúcgồmcácnodeliênkếtvớinhau thôngquacácmốiliênkết.Nodecuốilinkedlist đượcđặtlànullđểđánhdấukếtthúcdanhsách.• Linkedlistgiúptiếtkiệmbộnhớsovớimảngtrong cácbàitoánxửlýdanhsách.• Khichèn/xoámộtnodetrênlinkedlist,khôngphải dãn/dồncácphầntửnhưtrênmảng.• Việctruynhậptrênlinkedlistluônphảituầntự. 4LinkedList• ThểhiệnNodethôngqualớptựthamchiếu(self referentialclass) class Node { private int data; private Node nextNode; // constructors and methods ... } 15 10 5LinkedList• Mộtlinkedlistđượcquảnlýbởithamchiếutới nodeđầuvànodecuối. firstNode lastNode H D ... Q 6CàiđặtLinkedList//Dinhnghiamotnodetronglinkedlist classListNode{intdata;ListNodenextNode;ListNode(intvalue){ this(value,null);}ListNode(intvalue,ListNodenode){ data=value; nextNode=node;}intgetData() {returndata;}ListNodegetNext(){returnnextNode;}} 7CàiđặtLinkedList//DinhnghialopLinkedListpublicclassLinkedList{privateListNodefirstNode;privateListNodelastNode; publicLinkedList(){ firstNode=lastNode=null;}publicvoidinsertAtFront(intinsertItem){ if(isEmpty()) firstNode=lastNode=newListNode(insertItem); elsefirstNode=newListNode(insertItem,firstNode);} 8CàiđặtLinkedListpublicvoidinsertAtBack(intinsertItem){if(isEmpty())firstNode=lastNode=newListNode(insertItem);elselastNode=lastNode.nextNode=newListNode(insertItem);}publicintremoveFromFront(){intremoveItem=1;if(!isEmpty()){ removeItem=firstNode.data; if(firstNode==lastNode) firstNode=lastNode=null;else firstNode=firstNode.nextNode;}returnremoveItem;} 9CàiđặtLinkedListpublicintremoveFromBack(){ intremoveItem=1; if(!isEmpty()) { removeItem=lastNode.data; if(firstNode==lastNode) firstNode=lastNode=null; else { ListNodecurrent=firstNode; while(current.nextNode!=lastNode) current=current.nextNode; lastNode=current; current.nextNode=null; } } returnremoveItem;} 10CàiđặtLinkedListpublicbooleanisEmpty(){ return(firstNode==null);}publicvoidprint(){ ListNodenode=firstNode; while(node!=null) { System.out.print(node.data+); node=node.nextNode; } System.out.println( );}} 11MôtảinsertAtFront (a) firstNode 7 11 new ListNode 12 (b) firstNode 7 11 new ListNode 12 12MôtảinsertAtBack (a) firstNode lastNode new Li ...