| Revision as of 03:51, 11 December 2002 edit61.11.21.42 (talk)No edit summary← Previous edit | Revision as of 03:51, 11 December 2002 edit undo61.11.21.42 (talk)No edit summaryNext 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 ] 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). | |||
| 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 ''] 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. For example, in ]: | |||
| typedef struct Person | |||
| { | |||
| Person *prev; // <--- previous person in list | |||
| Person *next; // <--- next person in list | |||
| char name; | |||
| int age; | |||
| }; | |||
| An example of code that uses this structure: | |||
| Person first; // first item in the linked list | |||
| Person *p = &first;<br> | |||
| while(!feof(stdin)) // there's still input | |||
| { | |||
| p->next = (Person *)malloc(sizeof(Person)); // first link | |||
| p = p->next; | |||
| printf("Enter name and age:\n"); // Ask for input | |||
| scanf("%s %d", &(p->name), &(p->age)); // Use it | |||
| } | |||
| === Linked Lists On The Web === | |||
| Some linked list materials are available from the Stanford CS department: , and | |||