Chương 5 Danh sách liên kết (linked list)

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level 16/09/2013 ‹#› /20 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH DANH SÁCH LIÊN KẾT(Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Review Arrays Pros Access quickly via array index. Easier to use. Cons Fixed size: the size of the array is static. One block allocation Complex position-based insertion/removal 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 elements from any position in the sequence. Reference of the last node point to null. Only need to handle the first (head) element. (*) There might be two references, references can link to previous or next element. 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 advance 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? 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. 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) Danh sách liên kết vòng (Circular Linked List) Các phép toán trên Linked List public class Node { private T data; private Node next; public Node(T data, Node next) { this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public Node(T data) { this.data = data; } } Duyệt các phần tử Chèn them phần tử Chèn vào đầu Chèn vào giữa Xóa phần tử Xóa phần tử đầu Xóa phần tử giữa 1) Duyệt Node head = ...; Node current = head; while ((current = current.getNext()) != null) { System.out.println(current); } 2) Chèn phần tử Chèn vào đầu danh sách liên kết Chèn vào giữa danh sách liên kết 3) Xóa phần tử Xóa phần tử ở đầu danh sách Xóa phần tử ở giữa danh sách Danh sách liên kết kép (Doubly Linked List) Trong danh sách liên kết mà mỗi nút có 2 liên kết trỏ, 1 tới nút liền trước, 1 tới nút liền sau. Ưu điểm: Có thể duyệt theo cả hai chiều. Danh sách liên kết vòng (Circular Linked List) Trong danh sách liên kết đơn, nút cuối cùng của danh sách trỏ tới nút đầu tiên Ưu điểm: Bất kỳ nút nào cũng có thể coi là đầu danh sách Nhược điểm: Không biết lúc nào là kết thúc của danh sách A B C D E LinkedList Example LinkedList Node Node in different class Static inner class Node Non-static inner class Node 1. LinkedList public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } } 2. a) Node public class Node { private T data; private Node next; public Node(T data, Node next) { this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public Node(T data) { this.data = data; } } 2. b) Static inner class Node public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } private static class Node { private T data; private Node next; public Node(T data, Node next) { this.data = data; this.next = next; } } } 2. c) Non-static inner class Node public class LinkedList { private Node head; private String name; public LinkedList(Node head) { this.head = head; } public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } private class Node { private T data; private Node next; private String listName; public Node(T data, Node next) { this.data = data; this.next = next; this.listName = name; } } } Complexity: Array vs Linked List Operation Array Singly Linked List Indexing O(1) O(n) Insert/Delete at beginning O(n) O(1) Insert/Delete at end O(1) O(n) Insert/Delete in middle O(1) search time + O(1) Tóm tắt Review Arrays Introduce LinkedList Pros and cons Non-linear Linked List Classification of Linked List Các phép toán trên Linked List Danh sách liên kết kép Danh sách liên kết vòng Cài đặt LinkedList HỎI ĐÁP