Pertemuan 1, Pointer, Array and Introduction to Data Structure & Introduction to Linked List, 2101678775, Rafael Kevin Liman.

Introduction to Linked List

Sub Topics

Pointer, Array and Introduction to Data Structure

·        Array Review

·        Pointer Review

·        Types of Data Structures

Abstract Data Type

Array

•        A collection of similar data elements

•        These data elements have the same data type (homogenous)

•        The elements of the array are stored in consecutive memory locations and are referenced by an index

Array index starts from zero

Array Declaration & Accessing Array

•        One Dimensional Array

Declaration:

•        int arr[5];

Syntax:

type name[size];

An array of size N have indexes from 0 to N-1.

Accessing:

•        arr[0] = 7;

•        arr[1] = 2;

•        arr[2] = 13;

•        arr[3] = 13;

•        arr[4] = 13;

Two Dimensional Array

•        Declaration:

•        int arr[3][6];

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.

•        Accessing:

•        arr[0][2] = 2;

•        arr[2][1] = 9;

•        arr[1][5] = 13;

•        arr[2][4] = 10;

Multi Dimensional Array

•        Declaration:

•        int arr[4][3][7][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.

•        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;

Storing Array Values

Store values in the array

•        Initialize the elements

•        Input values for the elements

•        Assign values for the elements

Operations in Array

There are a number of operations that can be performed

on arrays. They are:

•        Traversal

•        Insertion

•        Searching

•        Deletion

•        Merging

•        Sorting

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

Data Structure          

•       A data structure is an arrangement of data, either in the computer’s memory or on the disk storage.

•        Some common examples of data structures include:

–       Arrays

–      A collection of similar data elements

–      Data elements have the same data type

–       Linked lists

–      A very dynamic data structure in which the elements can be added to or deleted from anywhere at will

–      Each element is called a node

–       Queues

–      The element that was inserted first is the first one to be taken out

–      The elements in a queue are added at one end called the rear and removed from the other end called the front

–       Stacks

–      Stacks can be represented as a linear array

–      Every stack has a variable TOP associated with it

–      LIFO (Last In First Out) / FILO (First In Last Out)

–       Binary trees

–      A data structure which is defined as a collection of elements called the nodes

–      Every node contains a left pointer, a right pointer, and a data element

–       Hash tables

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

•   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.

Introduction to Linked List

Sub Topics

Introduction to Linked List

-        Structure Declaration

-        Structure Assignments

-        Nested Structure

-        Array of Structure

-        Memory Allocation

-        Linked List Introduction

-        Linked List versus Array

Structure

• Structure is basically a user-defined data type that can store related information(evenof different data types) together, while an array can store only entities of same data types.

•   It is a collection of variables under a single name.

•   The variables within a structure are of different data types and each has a name that is used to select it from the structure.

 Structure Declaration

struct tdata {

          int   age;

          char  name[100];

          float score;

};

•    The code above defines a structure named tdata which has three members: age (int), name (char[]) and score (float).

•    Creating a variable of structure is similar to create a variable of primitive data type.

          tdata x;                  // a variable of tdata

          tdata arr[100];      // an array of tdata

Structure Assignments

tdata x;

You can use operator . (dot) to access member of x

x.age = 17;

strcpy(x.name, “andi”);

x.score = 82.5;

Memory Allocation: Dynamic

If you need to allocate memory dynamically (in runtime), you can

use malloc in C/C++. To de-allocate you can use free.

int  *px = (int *) malloc(sizeof(int));

char *pc = (char *) malloc(sizeof(char));

*px = 205;

*pc = ‘A’;

printf( “%d %c\n”, *px, *pc );

free(px);

free(pc);

Linked List versus Array

Array:

•        Linear collection of data elements

•        Store value in consecutive memory locations

•        Can be random in accessing of data

Linked List:

•        Linear collection of nodes

•        Doesn’t store its nodes in consecutive memory locations

•        Can be accessed only in a sequential manner