Page 87 - DCAP407_DATA_STRUCTURE

Data Structure

Did you know? Linked lists were developed in the year 1955-56 by Allen Newell, Cliff Shaw, and
Herbert Simon at RAND Corporation as a primary data structure. It was developed for
their Information Processing Language (IPL). IPL was used by the authors to develop
several early artificial intelligent programs, including Logic Theory Machine, the
General Problem Solver, and a computer chess program.
The advantage of using linked list is its ability to dynamically shrink and expand in size. This allows
you to insert or delete elements efficiently at any position in the list.

There are four types of linked lists namely, singly-linked list, doubly-linked list, circular list, and header
lists. Linked list is used as an Abstract Data Type (ADT) as it can store data of any type in nodes that are
interconnected to each other.
5.1 Basics of Linked List
The technique of dynamically implementing a list using pointers is known as linked list. Every element
in a list is represented as a node.

A train consists of several coaches that are interconnected to one another. Here,
a linked list represents a train and the coaches form the nodes in a list.

Figure 5.1 depicts a linked list consisting of four nodes.
Each node in figure 5.1 consists of two fields:
1. Data Field: It is a field that stores the element value of a specific data type in the list.
2. Link Field: It is a pointer field used to point to the next consecutive node thereby establishing a
link between two nodes. For example, in figure 5.1, the pointer field of Node1 holds the address of
Node2, the pointer field of Node2 holds the address of Node3, and so on.

Figure 5.1: Representation of a Linked List

Node1 Node2 Node3 Node4

Data field Data Data Data Data

Link field Pointer Pointer Pointer NULL

Holds Holds Holds
address of address of address of
node2 node3 node4

Each node holds the address of the next consecutive node and the pointer points to the data item in the
next node. In figure 5.1, the Node4 address is assigned a NULL value to depict the end of the list.

Did you know? Arrays follow a strategy of allocating memory for its elements in a single block of
memory. Whereas, linked lists allocate memory for each element individually. The
memory size increases as and when the data is added. This technique prevents
memory wastage.

80 LOVELY PROFESSIONAL UNIVERSITY