CH NG 4ƯƠ
DANH SÁCH TUY N TÍNHẾ
M C TIÊUỤ
Khái ni m danh sách tuy n tínhệ ế
Các phép toán v i danh sáchớ
L u tr k ti p c a danh sách tuy n tínhư ữ ế ế ủ ế
Danh sách móc n i đ nố ơ
Danh sách n i đôiố
Danh sách móc n i vòngố
Ngăn x pế
Hàng đ iợ
KHÁI NI M DSTTỆ
Danh sách là m t t p các ph n t thu c cùng m t ộ ậ ầ ử ộ ộ
l p đ i t ng nào đóớ ố ượ
Dãy s nguyên, danh sách sinh viên,...ố
Gi s L là m t danh sách có n ph n tả ử ộ ầ ử
L = { a1, a2, ..., an }
n g i là đ dài c a danh sách Lọ ộ ủ
n>0 thì a1 là ph n t đ u tiên, aầ ử ầ n là ph n t cu i cùngầ ử ố
V i L, ta nói aới đ ng tr c aứ ướ i+1 và đ ng sau aứi-1 (i=1...n).
Danh sách mà các ph n t có th t “ầ ử ứ ự tr c-sau”ướ g i là ọ
“DSTT”
CÁC PHÉP TOÁN TRÊN DSTT
Kh i t o danh sách r ng ở ạ ỗ (creat)
Ki m tra danh sách r ng ể ỗ (empty)
Ki m tra danh sách đ y ể ầ (full)
B sung m t ph n t vào danh sách ổ ộ ầ ử (add)
Lo i b m t ph n t kh i danh sách ạ ỏ ộ ầ ử ỏ (remove)
S p x p danh sách ắ ế (sort)
Tìm ki m trên danh sách ế(search)
...
L U TR K TI P C A DSTTƯ Ữ Ế Ế Ủ
DSTT đ c l u tr trong b nh b i m t m ng m t chi u ượ ư ữ ộ ớ ở ộ ả ộ ề
g i là l u tr k ti p.ọ ư ữ ế ế
M i ph n t c a m ng l u tr m t ph n t c a danh sáchỗ ầ ử ủ ả ư ữ ộ ầ ử ủ
u đi mƯ ể
Truy c p nhanh và đ ng đ u đ i v i m i ph n tậ ồ ề ố ớ ọ ầ ử
Các thao tác đ c th c hi n khá đ n gi nượ ự ệ ơ ả
Nh c đi mượ ể
Do kích th c m ng c đ nh khi khai báo nên có th d n đ n ướ ả ố ị ể ẫ ế
s lãng phí ho c thi u b nh .ự ặ ế ộ ớ