[Data Structure] Why we need Data Structure (Ex. File sharing system)

Library classification system

• method used in libraries or bookstores to systematically organize books and make them easy to find
• The main goal is to categorize books by subject and format and assign them a classification number, so both users and librarians can locate materials efficiently

 

Variants of library classification systems

Dewey Decimal Classification (DDC)

• the most widely used system
• divide human knowledge into 10 broad categories (000-900), which are further subdivided
• Ex) 500=Natural Sciences, 510=Mathematics, 520=Astronomy

Korean Decimal Classification (KDC)

• Based on DDC, but adapted to emphasize Korean history, Eastern philosophy, Buddhism, and other local features

 

 

Best seller section

Promotes easy access to popular books

• helps visitors quickly find popular titles without browsing through the entire catalog

Efficient space and resource managements

• Grouping them together makes it easier for staff to manage them
• Reduces congestion in other sections of the library

 

 

Definition of Data Sctructure

: collection of data values, the relationships among them, and the functions or operations that can be applied to the data

Ex) Phone book, Social Networks

 

 

Why do we need data structures?

• Efficient data management
• : Handling large scale data can lead to naive handling, which can occur inefficiency
• Performace depends on structure
• Foundation of computer science

 

 

Example - Searching Algorithm with different data types

Linear Search

// Pseudocode for Linearsearch
Algorithm LinearSearch(A, n, target):
  Input:
    A = array (unsorted list)
    n = number of elements in A
    target = value to search

  for i <- 0 to n-1 do 
    if A[i] = target then
      return i  // found at index i
  end for

  return -1  // not found

Binary Search

// Pseudo-code for BinarySearch

Algorithm BinarySearch(A, n, target):
  Input:
    A = sorted array
    n = number of elements in A
    target = value to search

  left <- 0
  right <- n-1

  while left<=right do
    mid <- (left+right)/2
    if A[mid] < target then
      return mid   // found at index mid
    else if A[mid] < target then 
      left <- mid+1
    else 
      right <- mid-1
  end while

  return -1  // not found

sorted array list에서, 일단 left가 첫 번째 값, right가 마지막 값, mid는 left와 right의 중간 값을 point하도록 설정한다.

만약 mid에 해당하는 값이 target보다 작으면, left를 mid 바로 오른쪽 값을 point하도록 변경한다.

만약 mid 값이 target보다 크면, right를 mid 바로 왼쪽 값을 point하도록 변경한다.

target 값을 찾을 때까지 이를 반복한다.

Binary Search with BST

// Pseudo-code for BinarySearch with BST

Algorithm  BST_Search(root, target):
  Input:
    root = root node of BST
    target = value to search

  current <- root

  while current != NULL do
    if current.key = target then 
      return current   // found
    else if target < current.key then
      current <- current.left
    else 
      current <- current.right
  end while

  return NULL   // not found

 

 

 

 

Real-word example - file sharing system

Server - Client structure

linear하게 전달되기 때문에, 다운로드하면서 볼 수 있다.

Peer-to-Peer (P2P) structure

Every Peer can be Seeder

Why do we need data structures?

• Develop Computational Thinking
• : trains us to break down problems, analyze patterns, think systematically
• Make Informed Decisions
• : Helps us decide which algorithm to use and which data structure best fits a given problem
• Create better Solutions