pertemuan ke-1 - Introduction to Data Structure - 2101640795 - Michael Kesta
Data
Structure
Array
Review
Array is a container
which can hold a fix number of items and these items should be of the same
type. Most of the data structures make use of arrays to implement their
algorithms. Following are the important terms to understand the concept of
Array.
·
Element −
Each item stored in an array is called an element.
·
Index −
Each location of an element in an array has a numerical index, which is used to
identify the element.
Array Representation
Arrays can be declared in various ways in different languages. For
illustration, let's take C array declaration.
As per the above illustration, following are the important points
to be considered.
·
Index starts with 0.
·
Array length is 10 which means it can store 10 elements.
·
Each element can be accessed via its index. For example, we can
fetch an element at index 6 as 9.
Array Declaration & Accessing array
•
One Dimensional Array
•
Declaration:
•
int arr[5];
•
Accessing:
•
arr[0] = 7;
•
arr[1] = 2;
•
arr[2] = 13;
•
arr[3] = 13;
•
arr[4] = 13;
Syntax:
type name[size];
An array of size N have indexes from 0 to
N-1.
•
Two Dimensional Array
• Declaration:
• int arr[4][3][7][10];
• Accessing:
• arr[0][2][2][9]= 2;
• arr[2][1][6][0]= 9;
• arr[3][0][0][6]= 13;
• arr[2][1][3][8]= 10;
Syntax:
type name[size1][size2];
• The
first index of array ranged from 0 to size1 – 1.
• The
second index of array ranged from 0 to size2 – 1.
• Multi Dimensional Array
• Declaration:
• int arr[4][3][7][10];
• Accessing:
• arr[0][2][2][9]= 2;
• arr[2][1][6][0]= 9;
• arr[3][0][0][6]= 13;
• arr[2][1][3][8]= 10;
Syntax:
type
ame[size1][size2][size3][...];
• The
first index of array ranged
from
0 to size1 – 1.
• The
second index of array ranged
from
0 to size2 – 1.
• The
third index of array ranged
from
0 to size3 – 1.
• and
so on.
How many dimension that can be stored in array ?
The
dimension of an array is the number of indices needed to select an element.
Thus, if the array is seen as a function on a set of possible index
combinations, it is the dimension of the space of which its domain is a
discrete subset. Thus a one-dimensional array is a list of data, a
two-dimensional array a rectangle of data, a three-dimensional array a block of
data, etc.
Pointer
Pointer is a data type whose value refers to
another value stored
elsewhere in computer memory using
its address.
The two most important operators used
with pointer type are:
•
& the
address operator
•
* the
dereferencing operator
•
If we have the declaration:
•
int
x;
•
int
*px;
•
then x is an integer and px is a
pointer to an integer. If we say:
•
px = &x;
•
then &x returns the address of x and
assigns it as the value of px.
•
To assign a value of x we can say
•
x
= 10;
•
or
•
*pi
= 10;
•
What
is the output of this program?
•
int a
= 10;
•
int *p = &a;
•
printf( “%d\n”, *p );
•
a
= 17;
•
*p = 20;
•
printf( “%d\n”, a );
DATA TYPE
• Data
Type is a
collection of objects and a set of operations that act on those objects.
• For example, the data type int consists of:
•
objects : 0, +1, -1, +2, -2, etc
•
operations : +, -, *, /, %, etc
• Example of predefined data types
are int,
char, float.
• Abstract
Data Type (ADT) is a
data type that is organized in such a way that the specification of the objects
and the specification of the operations on the objects is separated from the
representation of the objects and the implementation of the operations.
• C/C++ has a concept called class and struct which assist the programmer in implementing abstract data type.
Linked List
Like arrays, Linked List is a linear data structure. Unlike
arrays, linked list elements are not stored at contiguous location; the
elements are linked using pointers.
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
For example, in a system if we maintain a sorted list
of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to
maintain the sorted order, we have to move all the elements after 1000
(excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
Representation in C:
A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node
In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
Each node in a list consists of at least two parts:
1) data
2) pointer to the next node
In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
§ C
§ Java
§ Python
// A linked list node
struct Node
{
int data;
struct Node *next;
};
First Simple Linked List in C Let us create a simple linked list with 3 nodes.
§ C
§ Java
§ Python
// A simple C program to introduce
// a linked list
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
// Program to create a simple linked
// list with 3 nodes
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
/* Three blocks have been allocated dynamically.
We have pointers to these three blocks as first, second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
# represents any random value.
Data is random because we haven’t assigned anything yet */
head->data = 1; //assign data in first node
head->next = second; // Link first node with the second node
/* data has been assigned to data part of first block (block
pointed by head). And next pointer of first block points to
second. So they both are linked.
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
second->data = 2; //assign data to second node
second->next = third; // Link second node with the third node
/* data has been assigned to data part of second block (block pointed by
second). And next pointer of the second block points to third block.
So all three blocks are linked.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+ */
third->data = 3; //assign data to third node
third->next = NULL;
/* data has been assigned to data part of third block (block pointed
by third). And next pointer of the third block is made NULL to indicate
that the linked list is terminated here.
We have the linked list ready.
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
Note that only head is sufficient to represent the whole list. We can
traverse the complete list by following next pointers. */
return 0;
}
Komentar
Posting Komentar