Linked Data
Structures
Data Structure
• A data structure is a collection of data with well-defined
operations, behaviour, or features.
• A data structure in Java language is a special manner of storing
or organising data in java in computer memory so that we may
make good use of it.
Data Structures are used extensively in practically all areas of
computer science, including computer graphics, operating systems,
artificial intelligence, compiler design, and many more.
4-2
4-3
Objectives
• Understand linked structures
• Compare linked structures to array-
based structures
• Understand implementations for linked
structures
• Understand algorithms for managing a
linked list
Array Limitations
• Fixed size
• Physically stored in consecutive memory
locations, so to insert or delete items, may
need to shift data
Linked Data Structures
• A linked data structure consists of
items that are linked to other items
• Each item points to another item
Memory
Addr 1 Addr 2 Addr 3
Addr 2 Addr 3 null
data1 data2 data3
Linked Data Structures
• A linked data structure consists of
items that are linked to other items
• Each item points to another item
Memory
Addr 1 Addr 2 Addr 3
Addr 2 Addr 3 null
data1 data2 data3
Linear Linked Data Structures
• Singly linked list: each item points to the
next item
Memory
Addr 1 Addr 2 Addr 3
data1 data2 data2
Linked Data Structures
• Doubly linked list: each item points to
the next item and to the previous item
Memory
Addr 1 Addr 2 Addr 3
data1 data2 data2
4-9
Conceptual Diagram of a Singly-
Linked List
front
4-10
Advantages of Linked Lists
• The items do not have to be stored in
consecutive memory locations, so we
can insert and delete items without
shifting data.
4-11
Advantages of Linked Lists
front
Insert new data item here
4-12
Advantages of Linked Lists
front
4-13
Advantages of Linked Lists
Linked lists can grow and shrink dynamically
(i.e. at run time).
front
4-14
Nodes
• A linked list is an sequence of items called nodes
• A node in a singly linked list consists of two fields:
• A data portion
• A link (pointer) to the next node in the structure
• The first item (node) in the linked list is accessed via
a front or head pointer
front
data next
4-15
Implementation of Single Linked
List
class Node {
int x; // data to be stored
Node next; //a class datatype which
stores address
}
4-16
Questions(2 marks)
(i) A linked list is formed from the objects of
the class Node. The class structure of the
Node is given below:
class Node{ int n;
Node link; }
Write an algorithm or a method to count
only odd integers from an existing linked list.
4-17
4-18
Questions
(i) A linked list is formed from the objects of
the class Node. The class structure of the
Node is given below:
class Node{ int n;
Node link; }
Write an algorithm or a method to search for
a number from an existing linked list.
4-19
4-20
4-21
4-22
