Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 5: Danh sách liên kết trình bày về review arrays, linked list (Singly Linked List), pros and cons, non - linear linked list (Cấu trúc phi tuyến tính), classification of linked list, các phép toán trên linked list,...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân VinhGV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] DANH SÁCH LIÊN KẾTMÔN: CẤU TRÚC DỮ LIỆU (Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.6/12/14 edu.vn/201GV: NGUYỄN XUÂN VINH Review Arrays • Pros – Access quickly via array index. – Easier to use. • ConsMÔN: CẤU TRÚC DỮ LIỆU – Fixed size: the size of the array is static. – One block allocation – Complex position-based insertion/removal6/12/14/202GV: NGUYỄN XUÂN VINH Linked List (Singly Linked List) • A data structure consisting of a group of nodes which together represent a sequence  a linear structure. • Each node is composed of a data and a reference(*). • Allows more efficient insertion or removal of elementsMÔN: CẤU TRÚC DỮ LIỆU from any position in the sequence. • Reference of the last node point to null. • Only need to handle the first (head) element.6/12/14/20 (*) There might be two references, references can link to previous or next3GV: NGUYỄN XUÂN VINH Pros and cons • Pros – Flexibility: insert/delete from any position in constant time. – No single allocation of memory needed – Dynamic allocation: the size is not required to be known in advanceMÔN: CẤU TRÚC DỮ LIỆU q Cons – There is no index to query element directly  not allow random access to element – Complex to use and access. – No constant time access to the elements. Question: How to get the last element in the list?6/12/14/204GV: NGUYỄN XUÂN VINH Non-linear Linked List (Cấu trúc phi tuyến tính) • Normally, Linked List is a linear data structure. • However, the complex reference also be a non-linear structure such as Tree, Graph.MÔN: CẤU TRÚC DỮ LIỆU6/12/14/205GV: NGUYỄN XUÂN VINH Classification of Linked List • Danh sách liên kết đơn (Singly Linked List) • Danh sách liên kết kép (Doubly Linked List)MÔN: CẤU TRÚC DỮ LIỆU • Danh sách liên kết vòng (Circular Linked List)6/12/14/206GV: NGUYỄN XUÂN VINH Các phép toán trên Linked List public class Node { 1) Duyệt các phần tử private T data; 2) Chèn them phần tử private Node next; § Chèn vào đầu public Node(T data, § Chèn vào giữa Node next) {MÔN: CẤU TRÚC DỮ LIỆU 3) Xóa phần tử this.data = data; § Xóa phần tử đầu this.next = next; § Xóa phần tử giữa } public T getData() { return data; ...