Linked lists

Download c eBook

Remarks

The C language does not define a linked list data structure. If you are using C and need a linked list, you either need to use a linked list from an existing library (such as GLib) or write your own linked list interface. This topic shows examples for linked lists and double linked lists that can be used as a starting point for writing your own linked lists.

Singly linked list

The list contains nodes which are composed of one link called next.

Data structure

struct singly_node
{
  struct singly_node * next;
};

Doubly linked list

The list contains nodes which are composed of two links called previous and next. The links are normally referencing to a node with the same structure.

Data structure

struct doubly_node
{
  struct doubly_node * prev;
  struct doubly_node * next;
};

Topoliges

Linear or open

enter image description here

Circular or ring

enter image description here

Procedures

Bind

Bind two nodes together. enter image description here

void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
  prev->next = next;
  next->prev = prev;
}

Making circularly linked list

enter image description here

void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
  doubly_node_bind (head, head);
}

Making linearly linked list

enter image description here

void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
  head->prev = NULL;
  tail->next = NULL;
  doubly_node_bind (head, tail);
}

Insertion

Lets assume a empty list always contains one node instead of NULL. Then insertion procedures do not have to take NULL into consideration.

void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
  doubly_node_bind (prev, insertion);
  doubly_node_bind (insertion, next);
}

void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
  doubly_node_insert_between (tail->prev, tail, insertion);
}

void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
  doubly_node_insert_between (head, head->next, insertion);
}

Related Examples

Stats

334 Contributors: 11
Wednesday, September 28, 2016
Licensed under: CC-BY-SA

Not affiliated with Stack Overflow
Rip Tutorial: info@zzzprojects.com

Download eBook