Electronics and Computer Engineering
School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet - Hanoi - Vietnam
Data structure and Algorithms
LinkedList
Data structure and Algorithms
LinkedList
Thanh-Hai Tran
2020 2
Contents
Introduction
Pointers and Linked Storage Structures
Description of Linked Lists
Classification of Linked Lists:
Singly-Linked Lists
Doubly-Linked Lists
Implementation of LIFO, FIFO by Linked Storage
Structures
2020 3
3
Pointers
Concept of pointer: a data type used to point to address of
object (data object or function object)
Introduction
P
–Basic operations of pointers:
•Declaration:
•Take address of an object:
•Access to pointed object:
•Dynamic allocation of memory:
•Dynamic deallocation of memory:
int * P;
int A; P = &A;
*P = 20;
P = new int;
delete P;
A
2020 4
4
Linked Storage Structures
Organization of LSS:
Introduction
•Pointers: pointing to nodes
•Nodes: each contains information of an element of list and one or more
pointers
–Characteristics of LSS:
•Dynamic storage structure: memory allocation in run-time (on demand)
•Flexible arrangement: pointers can be easily changed to point to
different nodes
•Must have at least one access point: where the LSS can be accessed
from outside (as shown by P)
a2
a1a3
P
2020 5
5
Linked List: list implemented by LSS
Organization: 2 components:
Nodes: each contains information of an element of list and one
or more pointers pointing to other nodes.
Pointers: representing the linear relationships (before-after)
among elements. At least one special pointer plays role of
access point (like H).
Introduction
–Structure of a node: 2 parts:
•Information: storing value of an element of list
•Next: Pointer points to next node
–Header: a pointer (H) points to the first node of the list. It
plays role of access point.
info next
AC
H
B