链表
 | 此條 |
链表
历史[编辑]
链表开发于1955
结构[编辑]
单向链表[编辑]
链表
一个单向链表包含两个值:
一个单向链表的节点被分成两个部分。
链表
链表
双 向 链表[编辑]
一种更复杂的链表是“
一个双向链表有三个整数值:
循环链表[编辑]
循环链表
另外
块状链表[编辑]
块状链表
块状链表
其它扩展[编辑]
对于
存 储结构[编辑]
链表
共用 存 储空间- 链表
的 节点和 其它的 数 据 共用 存 储空间，优点是 可 以存储无限 多 的 内容 （不 过要处理器 支持 这个大小 ，并且存 储空间足够的情 况下），不 需要 提 前 分配 内 存 ；缺点 是 由 于内容 分散 ，有 时候可能 不 方便 调试。 独立 存 储空间- 一个链表或者多个链表使用独立的存储空间，
一般 用 数 组或 者 类似结构实现，优点是 可 以自动获得 一 个附加数 据 ：唯一 的 编号，并且方便 调试；缺点 是 不能 动态的 分配 内 存 。当然 ，另外的 在 上面 加 一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法 有 时候被 叫 做数 组模拟链表 ，但 是 事 实上只 是 用 表示 在 数 组中的 位置 的 下 标索引 代替 了 指向 内 存 地 址 的 指 针，这种下 标索引其实也是 逻辑上 的 指 针，整 个结构还是 链表，并不算 是 被 模 拟的（但 是 可 以说成 是 用 数 组实现的链表）。
链表的 应用[编辑]
链表
节点
C代 码实例 [编辑]
范例
接 口 声明 [编辑]
#ifndef LLIST_H
#define LLIST_H
typedef void node_proc_fun_t(void*);
typedef int node_comp_fun_t(const void*, const void*);
typedef void LLIST_T;
LLIST_T *llist_new(int elmsize);
int llist_delete(LLIST_T *ptr);
int llist_node_append(LLIST_T *ptr, const void *datap);
int llist_node_prepend(LLIST_T *ptr, const void *datap);
int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc);
void llist_node_delete(LLIST_T *ptr, node_comp_fun_t *comp, const void *key);
void *llist_node_find(LLIST_T *ptr, node_comp_fun_t *comp, const void *key);
#endif
接 口 实现[编辑]
类型定 义[编辑]
struct node_st {
void *datap;
struct node_st *next, *prev;
};
struct llit_st {
struct node_st head;
int lmsize;
int elmnr;
};
初 始 化 和 销毁[编辑]
LLIST_T *
llist_new(int elmsize) {
struct llist_st *newlist = malloc(sizeof(struct llist_st));
if (newlist == NULL)
return NULL;
newlist->head.datap = NULL;
newlist->head.next = &newlist->head;
newlist->head.prev = &newlist->head;
newlist->lmsize = elmsize;
return (void *)newlist;
}
int llist_delete(LLIST_T *ptr) {
struct llist_st *me = ptr;
struct node_st *curr, *save;
for (curr = me->head.next ;
curr != &me->head ; curr = save) {
save = curr->next;
free(curr->datap);
free(curr);
}
free(me);
return 0;
}
节点插入 [编辑]
int llist_node_append(LLIST_T *ptr, const void *datap) {
struct llist_st *me = ptr;
struct node_st *newnodep;
newnodep = malloc(sizeof(struct node_st));
if (newnodep == NULL)
return -1;
newnodep->datap = malloc(me->elmsize);
if (newnodep->datap == NULL) {
free(newnodep);
return -1;
}
memcpy(newnodep->datap, datap, me->elmsize);
me->head.prev->next = newnodep;
newnodep->prev = me->head.prev;
me->head.prev = newnodep;
newnodep->next = &me->head;
return 0;
}
int llist_node_prepend(LLIST_T *ptr, const void *datap) {
struct llist_st *me = ptr;
struct node_st *newnodep;
newnodep = malloc(sizeof(struct node_st));
if (newnodep == NULL)
return -1;
newnodep->datap = malloc(me->elmsize);
if (newnodep->datap == NULL) {
free(newnodep);
return -1;
}
memcpy(newnodep->datap, datap, me->elmsize);
me->head.next->prev = newnodep;
newnodep->next = me->head.next;
me->head.next = newnodep;
newnodep->prev = &me->head;
return 0;
}
遍 历[编辑]
int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc) {
struct llist_st *me = ptr;
struct node_st *curr;
for (curr = me->head.next;
curr != &me->head ; curr = curr->next)
proc(curr->datap); // proc(something you like)
return 0;
}
删除和 查找[编辑]
void llist_node_delete(LLIST_T *ptr,
node_comp_fun_t *comp,
const void *key) {
struct llist_st *me = ptr;
struct node_st *curr;
for (curr = me->head.next;
curr != &me->head; curr = curr->next) {
if ( (*comp)(curr->datap, key) == 0 ) {
struct node_st *_next, *_prev;
_prev = curr->prev; _next = curr->next;
_prev->next = _next; _next->prev = _prev;
free(curr->datap);
free(curr);
break;
}
}
return;
}
void *llist_node_find(LLIST_T *ptr,
node_comp_fun_t *comp, const void *key) {
struct llist_st *me = ptr;
struct node_st *curr;
for (curr = me->head.next;
curr != &me->head; curr = curr->next) {
if ( (*comp)(curr->datap, key) == 0 )
return curr->datap;
}
return NULL;
}
C宏 实例[编辑]
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list) {
list->next = list;
list->prev = list;
}
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next) {
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
static inline void list_add(struct list_head *new, struct list_head *head) {
__list_add(new, head, head->next);
}
static inline void __list_del(struct list_head *prev, struct list_head *next) {
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry) {
__list_del(entry->prev, entry->next);
entry->next = NULL;
entry->prev = NULL;
}
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
常 见用途 [编辑]
延伸 閲讀 [编辑]
- Juan, Angel. Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann) (PDF): 3. 2006 [2011-07-10]. （
原始 内容 (PDF)存 档于2012-01-06）. - Black, Paul E. Pieterse, Vreda; Black, Paul E. , 编. linked list. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. 2004-08-16 [2004-12-14]. （
原始 内容 存 档于2009-01-31）. - Antonakos, James L.; Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++. Prentice-Hall. 1999: 165–190. ISBN 0-13-280843-9.
- Collins, William J. Data Structures and the Java Collections Framework. New York: McGraw Hill. 2005: 239–303 [2002]. ISBN 0-07-282379-8.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. MIT Press. 2003: 205–213, 501–505. ISBN 0-262-03293-7.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 10.2: Linked lists. Introduction to Algorithms 2nd. MIT Press. 2001: 204–209. ISBN 0-262-03293-7.
- Green, Bert F., Jr. Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 1961, (2): 3–8. doi:10.1109/THFE2.1961.4503292.
- McCarthy, John. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. 1960, 3 (4): 184 [2021-03-15]. doi:10.1145/367177.367199. （
原始 内容 存 档于2013-10-04）. - Knuth, Donald. 2.2.3-2.2.5. Fundamental Algorithms 3rd. Addison-Wesley. 1997: 254–298. ISBN 0-201-89683-4.
- Newell, Allen; Shaw, F. C. Programming the Logic Theory Machine. Proceedings of the Western Joint Computer Conference. 1957: 230–240.
- Parlante, Nick. Linked list basics (PDF). Stanford University. 2001 [2009-09-21]. （
原始 内容 存 档 (PDF)于2009-03-17）. - Sedgewick, Robert. Algorithms in C
. Addison Wesley. 1998: 90–109. ISBN 0-201-31452-5. - Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. 1998: 77–102. ISBN 0-13-660911-2.
- Wilkes, Maurice Vincent. An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming (Pergamon Press). 1964, 4 (1): 1. doi:10.1016/0066-4138(64)90013-8.
- Wilkes, Maurice Vincent. Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM). 1964, (P–64): F1–1.
- Shanmugasundaram, Kulesh. Linux Kernel Linked List Explained. 2005-04-04 [2009-09-21]. （
原始 内容 存 档于2009-09-25）.
参 閲[编辑]
其他数 据 结构[编辑]
外部 链接[编辑]
- Description （页面
存 档备份，存 于互联网档案 馆） from the Dictionary of Algorithms and Data Structures - Introduction to Linked Lists （页面
存 档备份，存 于互联网档案 馆）, Stanford University Computer Science Library - Linked List Problems （页面
存 档备份，存 于互联网档案 馆）, Stanford University Computer Science Library - Open Data Structures - Chapter 3 - Linked Lists （页面
存 档备份，存 于互联网档案 馆）, Pat Morin - Patent for the idea of having nodes which are in several linked lists simultaneously (note that this technique was widely used for many decades before the patent was granted)
| |||||||||||||||||||||||||||||||||||||
|
