Data Structure Concepts

Definition

• DATA : collection of raw facts
• Data Structure : Representaion of logical relationship existing between individual elments of data

NEEDS

• To solve complex requirement
• To representation and organize
• Facilitates access and modification of data
• Formulating logical of mathematical description

Program = Algorithm + Data Structure

• Algorithm - step procedure
• Algo & DS ==> Independent

Classification of Data Structure

Primitive Data Structure

• directly operated upon the machine-level instruction
• Common types : Integer, Float, String, Boolean etc
• Create, Update, Select, Destroy or Delete

Non-Primitive Data Structure

• sophisticated Data Structures
• derived from primitive data Structures
• homogeneous(same type) or heterogeneous (different type)
• Traversal, Insertion, Selection, Searching, Sorting, Merging, Destroy or Delete

Types of Data Structure

abstract data type : 구현방법 명시x, 어떠한 연산에 대한 정의만

Linear Data Structure

• homogeneous elements
• sequence, linear series
• easy to implement (computer memory->lenear fashion)
• Stack, Queue, Linked lists

Stack

• abstract data type
• adding & removing : the top of the stack
• LIFO(Last in First out), FILO(First in Last out)
• push() : insert
• pop() : delete
• Stack-Overflow : full
• Stack-Underflow : empty

Undo mechanisms, Recursion/function calling, Expression conversion

Queue

• abstract data type, linear data structure
• REAR : where inserted first element is located
• FRONT : where removalexisting elements happens
• FIFO(First in First Out)
• enqueue() : inserting element in the rear
• dequeue() : removing element from the front
• peek() : return the value of first element without dequeuing it.

Hardware queues, Network routers, Operating sytems(CPU Schdulig), Airport take-off)

Linked List

• linear data structure, a group of nodes in a sequence
• node holds own data, the address of the next node <-chain-like structure
• Singly Linked List, Doubly Linked List, Circular linked List

Singly Linked List

• node : data & address(point to the next node)
• operation : insertion, deletion, tranversal.

Doubly Linked List

• node : previous & data & next

Circular Linked List

• last node holds the address of the first node

Making any list, Basic of dynamic memory allocation, efficient memory management

Non-Linear Data Structure

• connection with other data items
• hierarchical, parent child relationship
• not arranged in a sequential structure
• Trees, graphs

Binary Tree

• hierarchical data structure, each node has at most two childern
• left child, & right child
• node : pointer to left subtree & pointer to right subtree & information element
• Root : topmost node

• Root : P
• Nodes: 10
• Height or Tree : 3 (from 0)
• P : parent / Q & R : child

Rooted Binary Tree : root node, every node(at most the childeren)

Full Binary Tree

• children : 0 or 2

Perfect Binary Tree

• children : 2
• same leaf level

Complete Binary Tree

Balanced Binary Tree

Degenerated Tree

Searching, Time & Geography & Ancestry

Graph

• pictorial representation of a set of objects
• vertices(V) : points represents objects
• edges(E) : links connect the vertices
• Graph : a pair of sets(V,E)

Simple Graph

Directed Graph

• arrow

Weighted Graph

Bipartite Graph

Almost any complex problem, Network nodes