Revision as of 05:15, 14 January 2002 edit12.234.213.xxx (talk) Added links to Stanford linked list materials← Previous edit | Revision as of 06:12, 15 February 2002 edit undoConversion script (talk | contribs)10 editsm Automated conversionNext edit → | ||
Line 1: | Line 1: | ||
A '''linked list''' is one of the simplest ]s of ]. It consists of a number of ]s, each containing one element and one (or more) links to other nodes. Linked lists permit insertion and removal of nodes at any point in the list in ](1) time. Linked lists do not allow ]. | A '''linked list''' is one of the simplest ]s of ]. It consists of a number of ]s, each containing one element and one (or more) links to other nodes. Linked lists permit insertion and removal of nodes at any point in the list in ](1) time. Linked lists do not allow ]. | ||
The simplest kind of linked list is a ''singly linked list'', which has one link per node. This link points to the next node in the list, or to a ] value if it is the last node. This kind of list allows ] to elements only in one direction (from front to back). | The simplest kind of linked list is a ''singly linked list'', which has one link per node. This link points to the next node in the list, or to a ] value if it is the last node. This kind of list allows ] to elements only in one direction (from front to back). | ||
A more sophisticated kind of linked list is a ''doubly linked list''. Each node has two links, one to the previous node and one to the next. | A more sophisticated kind of linked list is a ''doubly linked list''. Each node has two links, one to the previous node and one to the next. | ||
This allows sequential access to the list in both directions. | This allows sequential access to the list in both directions. | ||
There are two significant variations to the types mentioned above. First is a ''circularly linked list'', where the first and last nodes are linked together. This can be done for both singly and doubly linked lists. The other variation is the addition of a ''] node'' at the beginning of the list. This node represents ''before the first node'' and/or ''after the last node'' of the list. It also makes it possible to have an empty list. | There are two significant variations to the types mentioned above. First is a ''circularly linked list'', where the first and last nodes are linked together. This can be done for both singly and doubly linked lists. The other variation is the addition of a ''] node'' at the beginning of the list. This node represents ''before the first node'' and/or ''after the last node'' of the list. It also makes it possible to have an empty list. | ||
Many ]s, such as ] have linked lists built in. In other languages it is simple to create the data structure using ] or ] to implement links between list nodes. | Many ]s, such as ] have linked lists built in. In other languages it is simple to create the data structure using ] or ] to implement links between list nodes. | ||
typedef struct Person | typedef struct Person | ||
{ | { | ||
Person *prev; <--- previous person in list | Person *prev; <--- previous person in list | ||
char *name; | char *name; | ||
int age; | int age; | ||
Person *next; <--- next person in list | Person *next; <--- next person in list | ||
}; | }; | ||
To declare: | To declare: | ||
Person *p = (Person *)malloc(sizeof(Person)); | Person *p = (Person *)malloc(sizeof(Person)); | ||
=== Linked Lists On The Web === | === Linked Lists On The Web === | ||
⚫ | Some linked list materials are available from the Stanford CS department : | ||
⚫ | Some |
||
Introduction to Linked Lists , and Linked List Problems | Introduction to Linked Lists , and Linked List Problems | ||
Revision as of 06:12, 15 February 2002
A linked list is one of the simplest data structures of computer programming. It consists of a number of nodes, each containing one element and one (or more) links to other nodes. Linked lists permit insertion and removal of nodes at any point in the list in O(1) time. Linked lists do not allow random access.
The simplest kind of linked list is a singly linked list, which has one link per node. This link points to the next node in the list, or to a null value if it is the last node. This kind of list allows sequential access to elements only in one direction (from front to back).
A more sophisticated kind of linked list is a doubly linked list. Each node has two links, one to the previous node and one to the next. This allows sequential access to the list in both directions.
There are two significant variations to the types mentioned above. First is a circularly linked list, where the first and last nodes are linked together. This can be done for both singly and doubly linked lists. The other variation is the addition of a sentinel node at the beginning of the list. This node represents before the first node and/or after the last node of the list. It also makes it possible to have an empty list.
Many programming languages, such as LISP have linked lists built in. In other languages it is simple to create the data structure using pointers or references to implement links between list nodes.
typedef struct Person
{
Person *prev; <--- previous person in list
char *name; int age;
Person *next; <--- next person in list };
To declare:
Person *p = (Person *)malloc(sizeof(Person));
Linked Lists On The Web
Some linked list materials are available from the Stanford CS department : Introduction to Linked Lists , and Linked List Problems