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,. | DANH SÁCH LIÊN KẾT (Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@ 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 One block allocation: if you don't have enough memory to provide a single block (but you have sufficient scattered memory blocks) to allocate the space for the array then you'll need to defragment and other similar stuff to first create a free block of that size. So you may like to term it as improper utilization of memory 2 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. (*) | DANH SÁCH LIÊN KẾT (Linked List) Nguyễn Xuân Vinh nguyenxuanvinh@ 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 One block allocation: if you don't have enough memory to provide a single block (but you have sufficient scattered memory blocks) to allocate the space for the array then you'll need to defragment and other similar stuff to first create a free block of that size. So you may like to term it as improper utilization of memory 2 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. (*): may 3 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) { = data; = next; } .
