Danh sách liên kết đơn – Lý thuyết cơ bản và cách triển khai

Khác với stack, queue danh sách liên kết đơn cũng là một kiểu danh sách tuyến tính gồm các phần tử vào lần lượt theo thứ tự tuy nhiên nó khác stack và queue ở chỗ là nó được cấp phát trong bộ nhớ bởi các phần tử rời rạc nhau, không nằm kề nhau, tuy nhiên giữa phần tử trước thì có 1 liên kết đến phần tử sau nó.

Các thao tác trên danh sách liên kết đơn(single-link list)

1.Định nghĩa tổng quát

</div>
<div id="cviet_code_903">struct tq {
thtin_t phantu;
struc tq*tiep;
};
typedef struct tq tq_t;</div>
<div>

2.Con trỏ tới 1 node

</div>
<div id="cviet_code_901">struct  node {
int infor;
struct node *next;
};
typedef struct node *NODEPTR;</div>
<div>

3.Cấp phát bộ nhớ cho 1 node

</div>
<div id="cviet_code_1164">NODEPTR Getnode(void) {
NODEPTR p;
P = (NODEPTR) <a href="http://cppreference.com/stdmem/malloc.html" target="_blank">malloc</a>(sizeof( struct node));
Return(p);
}</div>
<div>

4.Giải phóng 1 node

</div>
<div id="cviet_code_911">NODEPTR Freenode( NODEPTR p){
<a href="http://cppreference.com/stdmem/free.html" target="_blank">free</a>(p);
}</div>
<div>

5.Thêm phần tử vào đỉnh danh sách

</div>
<div id="cviet_code_804">void Push_Top( NODEPTR *plist, int x) {
NODEPTR p;
p= Getnode();
p -> infor = x;
p ->next = *plist;
*plist = p;
}</div>
<div>

6.Thêm node mới vào cuối danh sách

</div>
<div id="cviet_code_922">void Push_Bottom( NODEPTR *plist, int x) {
NODEPTR p, q;
p= Getnode(); //
p->infor = x;
q = *plist;
while (q-> next != NULL)
q = q -> next;

q -> next = p;
p ->next = NULL;
}</div>
<div>

7.Thêm node mới vào giữa danh sách

</div>
<div id="cviet_code_1439">void Push_Before( NODEPTR p, int x ){
NODEPTR q;
if (p->next==NULL)
Push_Bottom(p, x);
else {
q= Getnode();
q -> infor = x;
q-> next = p-> next;
p->next = q;
}
}</div>
<div>

8.Xóa 1 node đầu danh sách

</div>
<div id="cviet_code_1236">void Del_Top( NODEPTR *plist) {
NODEPTR p;
p = *plist;
if (p==NULL) return;
(*plist) = (*plist) -> next;
p-> next = NULL;
Freenode(p);
}</div>
<div>

9.Xóa node cuối danh sách

</div>
<div id="cviet_code_1528">void Del_Bottom(NODEPTR *plist) {
NODEPTR p, q;
if (*plist==NULL) return;
else if ( (*plist)->next==NULL))
Del_Top(plist);
else {
p = *plist;
while (p->next!=NULL){
q = p;
p = p->next;
}
// p lµ node cuèi danh s¸ch;
q->next =NULL;
Freenode(p);
}
}</div>
<div>

10.Xóa node giữa danh sách

</div>
<div id="cviet_code_1531">void Del_before(NODEPTR p){
NODEPTR q;
if (p->next==NULL) return;
q = p ->next;
p->next = q->next;
Freenode(q);
}</div>
<div>

Ngoài ra các thao tác duyệt danh sách, tìm kiếm trên danh sách…