![](images/graphics/blank.gif)
Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân Vinh
lượt xem 9
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
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,...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 5 - Nguyễn Xuân Vinh
- GV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] DANH SÁCH LIÊN KẾT MÔN: CẤU TRÚC DỮ LIỆU (Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf. 6/12/14 edu.vn /20 1
- GV: NGUYỄN XUÂN VINH Review Arrays • Pros – Access quickly via array index. – Easier to use. • Cons MÔN: CẤU TRÚC DỮ LIỆU – Fixed size: the size of the array is static. – One block allocation – Complex position-based insertion/removal 6/12/14 /20 2
- GV: 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 elements MÔ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 next 3
- GV: 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 advance MÔ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 /20 4
- GV: 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ỆU 6/12/14 /20 5
- GV: 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 /20 6
- GV: 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; } 6/12/14 public void setData(T data) { /20 this.data = data; 7 }
- GV: NGUYỄN XUÂN VINH 1) Duyệt Node head = ...; Node current = head; while ((current = current.getNext()) != null) { System.out.println(current); MÔN: CẤU TRÚC DỮ LIỆU } 6/12/14 /20 8
- GV: NGUYỄN XUÂN VINH 2) Chèn phần tử Chèn vào đầu danh sách liên kết MÔN: CẤU TRÚC DỮ LIỆU Chèn vào giữa danh sách liên kết 6/12/14 /20 9
- GV: NGUYỄN XUÂN VINH 3) Xóa phần tử Xóa phần tử ở đầu danh sách MÔN: CẤU TRÚC DỮ LIỆU Xóa phần tử ở giữa danh sách 6/12/14 /20 10
- GV: NGUYỄN XUÂN VINH 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. MÔN: CẤU TRÚC DỮ LIỆU • Ưu điểm: – Có thể duyệt theo cả hai chiều. 6/12/14 /20 11
- GV: NGUYỄN XUÂN VINH Danh sách liên kết vòng (Circular Linked List) danh sách liên kết đơn, nút cuối cùng của danh sách trỏ tới • Trong nút đầu tiên A B C D E MÔN: CẤU TRÚC DỮ LIỆU • Ư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 6/12/14 /20 12
- GV: NGUYỄN XUÂN VINH LinkedList Example 1. LinkedList 2. Node a) Node in different class b) Static inner class Node MÔN: CẤU TRÚC DỮ LIỆU c) Non-static inner class Node 6/12/14 /20 13
- GV: NGUYỄN XUÂN VINH 1. LinkedList public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } public Node getHead() { return head; MÔN: CẤU TRÚC DỮ LIỆU } public void setHead(Node head) { this.head = head; } } 6/12/14 /20 14
- GV: NGUYỄN XUÂN VINH 2. a) Node public class Node { private T data; private Node next; public Node(T data, Node MÔN: CẤU TRÚC DỮ LIỆU next) { this.data = data; this.next = next; } public T getData() { return data; 6/12/14 } /20 public void setData(T data) { 15
- GV: NGUYỄN XUÂN VINH 2. b) Static inner class Node public class LinkedList { private Node head; public LinkedList(Node head) { this.head = head; } MÔN: CẤU TRÚC DỮ LIỆU public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } 6/12/14 private static class Node { private T data; /20 private Node next; 16 public Node(T data, Node next) {
- GV: NGUYỄN XUÂN VINH 2. c) Non-static inner class Node public class LinkedList { private Node head; private String name; public LinkedList(Node head) { this.head = head; MÔN: CẤU TRÚC DỮ LIỆU } public Node getHead() { return head; } public void setHead(Node head) { this.head = head; 6/12/14 } private class Node { /20 private T data; 17
- GV: NGUYỄN XUÂN VINH Complexity: Array vs Linked List Operation Array Singly Linked List Indexing O(1) O(n) MÔN: CẤU TRÚC DỮ LIỆU 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) 6/12/14 /20 18
- GV: NGUYỄN XUÂN VINH Tóm tắt • Review Arrays • Introduce LinkedList • Pros and cons • Non-linear Linked List MÔN: CẤU TRÚC DỮ LIỆU • 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 6/12/14 /20 19
- 20 /20 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH HỎI ĐÁP
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu & thuật toán: Chương 3 - Nguyễn Đức Nghĩa
0 p |
503 |
166
-
Bài giảng Cấu trúc dữ liệu cơ bản và giải thuật - Chương 1
9 p |
269 |
29
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p |
186 |
17
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Bích Diệp
28 p |
127 |
10
-
Bài giảng Cấu trúc dữ liệu: Chương 10 - Nguyễn Xuân Vinh
31 p |
102 |
10
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p |
171 |
9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p |
92 |
9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p |
123 |
9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p |
99 |
8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p |
82 |
8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p |
69 |
7
-
Bài giảng Cấu trúc dữ liệu: Chương Giới thiệu - Nguyễn Xuân Vinh
8 p |
120 |
7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p |
101 |
6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p |
187 |
6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p |
114 |
4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Châu Thị Bảo Hà
133 p |
117 |
4
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
10 p |
81 |
4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các khái niệm cơ bản
23 p |
55 |
3
![](images/icons/closefanbox.gif)
![](images/icons/closefanbox.gif)
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn
![](https://tailieu.vn/static/b2013az/templates/version1/default/js/fancybox2/source/ajax_loader.gif)