INSTITUTE OF ENGINEERING AND TECHNOLOGY
T. M. Palayam, Coimbatore-641 105
(Approved by AICTE, New Delhi and Affiliated to Anna University, Chennai)
Accredited by NAAC “A+”, Recognized by UGC under Section 2(f) and 12(B)
NBA ACCRDIATED COURSES: AERO&CSE
UNIT – II
LINEAR DATA STRUCTURES - LIST
What is a Data Structure?
A Data Structure is a collection of data elements which defines the way of storing and
organizing data in a computer so that it can be used efficiently.
It comprises of
• a collection of data elements
• the relationships among them and
• the functions or operations that can be applied to the data.
Why is Data Structure needed?
• It influences the ability of a computer to store/retrieve data to/from any location in the
memory.
• It enables a computer system to perform its task more efficiently.
Classification of Data Structures
Data structures can be classified into two classes namely:
Primitive data structures and Non-Primitive data structures.
A primitive data structure refers to the fundamental data types which are supported by a
programming language. Examples are integer, real, character, and boolean. Non-primitive
data structures are created using primitive data structures.
Non-primitive data structures can further be classified into two categories:
Linear data structures and Non-linear data structures.
If the elements of a data structure are stored in a linear or sequential order, then it is a linear
data structure. Examples are arrays, linked lists, stacks, and queues. Linear data structures can
be implemented in memory in two different ways. One way is to use an array based
implementation and the other is to use a linked list implementation.
If the elements of a data structure are not stored in a sequential order, then it is a non-linear
data structure. Examples are trees and graphs.
ABSTRACT DATA TYPES (ADTs)
An abstract data type (ADT) is a set of operations. Abstract data types are mathematical
abstractions. They do not mention how the set of operations is implemented.
, An ADT is as an extension of modular design.
Modularity has two advantages :
1. Debugging is easier
2. Many people can work on the modular program simultaneously.
Examples:
Data structures such as lists, stacks, queues, trees and graphs along with their operations, can
be viewed as abstract data types.
Fig: 1.2 An array of 6 elements represented in memory
Limitations of Arrays:
1. Arrays are of fixed size.
2. Contiguous memory locations may not be always available.
3. Insertion and deletion are quite difficult in an array as the elements are stored in
consecutive memory locations and the shifting operation is costly.
To overcome the limitations of arrays, we use linked lists.
LIST ADT
A list is of the form a1,a2,a3,a4,… ............ ,an. The size of the list is n. The first element of the list
is a1 and an is the last element. The position of element ai in a list is i. A list of size 0 is called as a
null list. Some of the operations that can be performed on a list are insert,
delete, find, print etc. Let us look at the operations with the help of an example. If the list
contains the following elements 34,82,14,62,18,12 then
• find(13) returns 3
• insert(72,4) makes the list into 34,82,14,62,72,18,12 (i.e) 72 is inserted after position
4.
• delete(18) makes the list into 34,82,14,62,72,12.
Array Implementation of Lists #
assigning elements to list list1 =[]
for i in range(0, 11):
list1.append(i)
# accessing elements from a list for
i in range(0, 11):
print(list1[i])
Deletion from a list
list1 = [1, 2, 3, 4, 5]
, print(list1)
# deleting element
del list1[2]
print(list1)
Note : Arrays are generally not used to implement lists as the insertions and deletions is time
consuming and expensive due to the shifting operation involved and the list size must also be known
in advance.
LINKED LIST
• The linked list consists of a series of nodes, which are not necessarily
adjacent in
memory.
• Each node contains two fields namely the data element and a pointer(called as the
next pointer) to the next node as shown in Fig 1.3.
• The next pointer of t he last node in the list points to NULL.
Data Next
element pointer
Fig Structure of a node in a linked list
Fig A Linked List
(Adapted from “Data Structures and Algorithm in Python” )
In Fig 1.4, the linked list consists of 5 elements a1,a2,a3,a4,a5 respectively. Let us
Fig : Linked List with actual pointer values
assume that these 5 nodes reside in memory locations 890,496,345,900,254
respectively. Then we can represent our linked list as shown in Fig 1.5.
T. M. Palayam, Coimbatore-641 105
(Approved by AICTE, New Delhi and Affiliated to Anna University, Chennai)
Accredited by NAAC “A+”, Recognized by UGC under Section 2(f) and 12(B)
NBA ACCRDIATED COURSES: AERO&CSE
UNIT – II
LINEAR DATA STRUCTURES - LIST
What is a Data Structure?
A Data Structure is a collection of data elements which defines the way of storing and
organizing data in a computer so that it can be used efficiently.
It comprises of
• a collection of data elements
• the relationships among them and
• the functions or operations that can be applied to the data.
Why is Data Structure needed?
• It influences the ability of a computer to store/retrieve data to/from any location in the
memory.
• It enables a computer system to perform its task more efficiently.
Classification of Data Structures
Data structures can be classified into two classes namely:
Primitive data structures and Non-Primitive data structures.
A primitive data structure refers to the fundamental data types which are supported by a
programming language. Examples are integer, real, character, and boolean. Non-primitive
data structures are created using primitive data structures.
Non-primitive data structures can further be classified into two categories:
Linear data structures and Non-linear data structures.
If the elements of a data structure are stored in a linear or sequential order, then it is a linear
data structure. Examples are arrays, linked lists, stacks, and queues. Linear data structures can
be implemented in memory in two different ways. One way is to use an array based
implementation and the other is to use a linked list implementation.
If the elements of a data structure are not stored in a sequential order, then it is a non-linear
data structure. Examples are trees and graphs.
ABSTRACT DATA TYPES (ADTs)
An abstract data type (ADT) is a set of operations. Abstract data types are mathematical
abstractions. They do not mention how the set of operations is implemented.
, An ADT is as an extension of modular design.
Modularity has two advantages :
1. Debugging is easier
2. Many people can work on the modular program simultaneously.
Examples:
Data structures such as lists, stacks, queues, trees and graphs along with their operations, can
be viewed as abstract data types.
Fig: 1.2 An array of 6 elements represented in memory
Limitations of Arrays:
1. Arrays are of fixed size.
2. Contiguous memory locations may not be always available.
3. Insertion and deletion are quite difficult in an array as the elements are stored in
consecutive memory locations and the shifting operation is costly.
To overcome the limitations of arrays, we use linked lists.
LIST ADT
A list is of the form a1,a2,a3,a4,… ............ ,an. The size of the list is n. The first element of the list
is a1 and an is the last element. The position of element ai in a list is i. A list of size 0 is called as a
null list. Some of the operations that can be performed on a list are insert,
delete, find, print etc. Let us look at the operations with the help of an example. If the list
contains the following elements 34,82,14,62,18,12 then
• find(13) returns 3
• insert(72,4) makes the list into 34,82,14,62,72,18,12 (i.e) 72 is inserted after position
4.
• delete(18) makes the list into 34,82,14,62,72,12.
Array Implementation of Lists #
assigning elements to list list1 =[]
for i in range(0, 11):
list1.append(i)
# accessing elements from a list for
i in range(0, 11):
print(list1[i])
Deletion from a list
list1 = [1, 2, 3, 4, 5]
, print(list1)
# deleting element
del list1[2]
print(list1)
Note : Arrays are generally not used to implement lists as the insertions and deletions is time
consuming and expensive due to the shifting operation involved and the list size must also be known
in advance.
LINKED LIST
• The linked list consists of a series of nodes, which are not necessarily
adjacent in
memory.
• Each node contains two fields namely the data element and a pointer(called as the
next pointer) to the next node as shown in Fig 1.3.
• The next pointer of t he last node in the list points to NULL.
Data Next
element pointer
Fig Structure of a node in a linked list
Fig A Linked List
(Adapted from “Data Structures and Algorithm in Python” )
In Fig 1.4, the linked list consists of 5 elements a1,a2,a3,a4,a5 respectively. Let us
Fig : Linked List with actual pointer values
assume that these 5 nodes reside in memory locations 890,496,345,900,254
respectively. Then we can represent our linked list as shown in Fig 1.5.
