讲真，链表是个十分入门且简单的数据结构，虽然用的不多，但有时候还真非它莫属。
然而，作为一名C++选手，我的链表总是被各种大常数以及难写的代码困扰。
今天从算法导论上学来了点小技巧，赶紧代码实现了一下。
之前，我的链表都是这么写的。
class list { struct node { int key; node *next; node *prev; }; node *head; node *tail; list(void) { head = NULL; tail = NULL; } void insert_to_head(int k) { node *t = new node; t -> key = k; t -> prev = NULL; t -> next = head; if (head != NULL) head -> prev = t; head = t; } void insert_to_tail(int k) { node *t = new node; t -> key = k; t -> prev = tail; t -> next = NULL; if (tail != NULL) tail -> next = t; tail = t; } void delete_a_node(node *t) { if (t -> prev != NULL) t -> prev -> next = t -> next; else head = t -> next; if (t -> next != NULL) t -> next -> prev = t -> prev; else tail = t -> prev; delete(t); } node *find_the_key(int k) { node *t = head; while (t != NULL && t -> key != k) t = t -> next; return t; } };
代码还是蛮好看的，自认为。然而接连不断地新建结点的常数总是让人吃不消。
于是，从Introduction to Algorithm中学来的第一招——用哨兵（哑结点）优化常数以及代码难度。
原来，我们经常用到一个表示空结点的NULL，而且为了防止非法访问，还要各种边界特判，烦不胜烦。
现在，我们新建一个名为NIL的哑结点，用来替代原来的所有NULL，省去了好多特判，代码也好写多了。重点是还能通过NIL把head和tail连在一起，形成了一个环状链表。
class list { struct node { int key; node *next; node *prev; }; node *nil; list(void) { nil = new node; nil -> key = -1; nil -> next = nil; nil -> prev = nil; } void insert_to_head(int k) { node *t = new node; t -> key = k; t -> prev = nil; t -> next = nil -> next; t -> next -> prev = nil -> next = t; } void insert_to_tail(int k) { node *t = new node; t -> key = k; t -> next = nil; t -> prev = nil -> prev; t -> prev -> next = nil -> prev = t; } void delete_a_node(node *t) { t -> prev -> next = t -> next; t -> next -> prev = t -> prev; delete(t); } node *find_the_key(int k) { node *t = nil -> next; while (t != nil && t -> key != k) t = t -> next; return t; } };
后来，看到算法导论还说我们可以自己手写新建结点和释放结点函数，实现垃圾回收，感觉会快很多呢。我就顺便扩展了一下，实现了自动申请新的更多的空间。
class list { struct node { int key; node *next; node *prev; }; const static int lim = 1000000; node *nil; node *fre; void apply_more(void) { node *lst = new node[lim]; for (int i = 0; i < lim; ++i) { lst[i].next = fre; fre = lst + i; } } node *new_node(void) { if (fre == NULL) apply_more(); node *ret = fre; fre = fre -> next; return ret; } void free_node(node *t) { t -> next = fre; fre = t; } list(void) { fre = NULL; nil = new_node(); nil -> key = -1; nil -> next = nil; nil -> prev = nil; } void insert_to_head(int k) { node *t = new_node(); t -> key = k; t -> prev = nil; t -> next = nil -> next; t -> next -> prev = nil -> next = t; } void insert_to_tail(int k) { node *t = new_node(); t -> key = k; t -> next = nil; t -> prev = nil -> prev; t -> prev -> next = nil -> prev = t; } void delete_a_node(node *t) { t -> prev -> next = t -> next; t -> next -> prev = t -> prev; free_node(t); } node *find_the_key(int k) { node *t = nil -> next; while (t != nil && t -> key != k) t = t -> next; return t; } };
@Author: YouSiki