Each record of a linked list is often called an element or node. The field of each node that contains address of the next node is usually called the next link or next pointer. The remaining fields may be called the data, information, value, or payload fields.
The head of a list is its first node, and the tail is the list minus that node (or a pointer thereto). In Lisp and some derived languages, the tail may be called the CDR (pronounced could-R) of the list, while the payload of the head node may be called the CAR.
Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages, these lists are constructed from nodes, each called a cons or cons cell. The cons has two fields: the car, a reference to the data for that node, and the cdr, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.
In languages that support Abstract data types or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using references together with records. Here is a complete example in C:
#include /* for printf */
#include /* for malloc */typedef struct node {
int data;
struct node *next; /* pointer to next element in list */
} LLIST;LLIST *list_add(LLIST **p, int i);
void list_remove(LLIST **p);
LLIST **list_search(LLIST **n, int i);
void list_print(LLIST *n);LLIST *list_add(LLIST **p, int i)
{
LLIST *n = (LLIST *) malloc(sizeof(LLIST));
if (n == NULL)
return NULL;n->next = *p; /* the previous element (*p) now becomes the “next” element */
*p = n; /* add new empty element to the front (head) of the list */
n->data = i;return *p;
}void list_remove(LLIST **p) /* remove head */
{
if (*p != NULL)
{
LLIST *n = *p;
*p = (*p)->next;
free(n);
}
}LLIST **list_search(LLIST **n, int i)
{
while (*n != NULL)
{
if ((*n)->data == i)
{
return n;
}
n = &(*n)->next;
}
return NULL;
}void list_print(LLIST *n)
{
if (n == NULL)
{
printf(”list is empty\n”);
}
while (n != NULL)
{
printf(”print %p %p %d\n”, n, n->next, n->data);
n = n->next;
}
}int main(void)
{
LLIST *n = NULL;list_add(&n, 0); /* list: 0 */
list_add(&n, 1); /* list: 1 0 */
list_add(&n, 2); /* list: 2 1 0 */
list_add(&n, 3); /* list: 3 2 1 0 */
list_add(&n, 4); /* list: 4 3 2 1 0 */
list_print(n);
list_remove(&n); /* remove first (4) */
list_remove(&n->next); /* remove new second (2) */
list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */
list_remove(&n->next); /* remove second to last node (0) */
list_remove(&n); /* remove last (3) */
list_print(n);return 0;
}
Author:Time:Monday, July 27th, 2009 at 5:57 pmCategory:Comments:You can leave a response, or trackback from your own site.RSS:You can follow any responses to this entry through the RSS 2.0 feed.Navigation: