Why do we need linked lists

Sequential table construction needs to know the size of the data in advance to apply for continuous storage space, and data relocation during expansion (insertion, deletion), so it is not very flexible to use.

Linked list structure can make full use of computer memory space and realize flexible memory dynamic management.


Definition of linked list

Linked list is a common basic data structure. It is a chained storage structure of linear tables. The storage address space does not need to be continuous, but each node (data storage unit) stores the location information (i.e. address) of the next node.


Terminology related to chain storage

  • Node: Storage image of data element. It consists of two parts: data domain and address domain.
  • Linked list: N nodes form a linked list of pointer chains. It is a chain storage image of a linear list, called the chain storage structure of a linear list.


Singly linked list

A one-way list, also known as a singly linked list, is the simplest form of a linked list in which each node contains two fields, a data field and a link field (address field). The link points to the next node in the list, and the link field of the last node points to a NULL value (usually NULL or ^).

  • Data fieldsdataUsed to store specific data.
  • Link domainnextThe location used to store the next node.
  • LPoints to the position of the first node of the list, fromLStart to find any node in the table.


Unidirectional cyclic linked lists

  • Data fieldsdataUsed to store specific data.
  • The address fieldnextTo store the location of the next node,But the address field of the last node stores the address of the linked list header.

** Advantages: ** Starting from any node in the list can find other nodes in the list.


Two-way linked list

A more complex type of list is a bidirectional list. Each node has two links: one to the previous node (null if it is the first node) and the other to the next node (null if it is the last node).

  • Data fieldsdataUsed to store specific data.
  • The address fieldpreThe location used to store the previous node, the address fieldnextThe location used to store the next node.

Advantages: convenient to find a linked list of nodes in a node of the precursor node.


A small extension

The head pointer

  • A header pointer is a pointer to the first node in the list, or to the first node if the list has a header.
  • Header Pointers are used as identifiers, so they are often preceded by the name of the linked list.
  • Whether the list is empty or not, the head pointer is not empty. A header pointer is a necessary element of a linked list.


The first node

  • The header node is set up for unity and convenience of operation. It is placed before the node of the first element and its data field is generally meaningless (it can also store the length of the linked list).
  • With a header, inserting and deleting the first element before the first element is done in the same way as any other node.
  • A header is not necessarily a list element.


The source code

The source code has been uploaded to GitHub data-structure-of-C, welcome to visit.

✍ code word is not easy, the long journey always feeling, praise again go line, also hope you heroes support ❤️