자료구조

• 자료구조는 데이터를 효율적으로 사용할 수 있도록 데이터를 저장하고 구성하는 방법.

1. 선형구조

• 선형 리스트 (Array)
  • 배열은 연속해있는 데이터의 집합
  • 각 데이터는 index를 가지며, n개를 원소로 가지는 배열일 때 순서대로 0 ~ n-1
  • 배열은 고정된 크기를 가지는 자료 구조
  • Array의 시간복잡도
    • Access : O(1)
    • Search : O(n)
    • Insertion : O(n)
    • Deletion : O(n)

 

• 연결 리스트 (Linked List)
  • 연결 리스트는 요소가 연속적인 메모리 위치에 저장되지 않는 자료 구조.
  • LinkedList는 각 원소가 다음 index 위치에 해당하는 물리적 주소를 가지고 있음.
  • 삽입/삭제시에는 데이터를 Shift할 필요 없이, 해당되는 원소의 물리적 주소만 변경해주면 됨.
  • 하지만 이 같은 특징 때문에 원하는 index를 참조하려면, 1번 index부터 차례대로 접근해야 한다는 비효율성이 있음.
  • Linked List의 시간복잡도
    • Access : O(n)
    • Search : O(n)
    • Insertion : O(1)
    • Deletion : O(1)

 

 

• 스택 (Stack)
  • FILO(First In Last Out)을 기본으로 구현된 자료구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
  • Stack의 시간복잡도
    • Access : O(n) (peek은 O(1))
    • Search : O(n)
    • Insertion (push) : O(1)
    • Deletion (pop) : O(1)

 

• 큐 (Queue)
  • FIFO의 자료구조
  • 데이터가 들어오는 위치는 가장 뒤에 있고, 데이터가 나가는 위치는 가장 앞에 있어서, 먼저 들어오는 데이터가 먼저 나가게 됨.
  • Queue의 시간복잡도
    • Access : O(n) (peek은 O(1))
    • Search : O(n)
    • Insertion (push) : O(1)
    • Deletion (pop) : O(1)

• 덱 (Deque; Double Ended Queue)
  • 양쪽에서 모두 입력과 출력이 가능한 자유도가 스택과 큐에비해서 높은 자료구조
  • Deque의 시간복잡도
    • Access : O(n) (peek은 O(1))
    • Search : O(n)
    • Insertion (push) : O(1)
    • Deletion (pop) : O(1)

 

 

2. 비선형구조

• 그래프 (Graph)
  • 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조.
  • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조.
  • 그래프를 구현하는 방법 2가지
    • 인접 리스트 (Adjacency List)

    

    • 인접 행렬

    

     

• 트리 (Tree)
  • 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조
  • 이진 트리 (Binary Tree)
    • 부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는, 트리의 가장 간단한 형태 
    • Perfect Binary Tree : 모든 단말 노드가 같은 level인 트리
    • Full Binary Tree : 단말 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리
    • Complete Binary Tree : 포화 이진 트리에서 오른쪽 단말 노드부터 제거해 나간 트리

    

  • 이진 탐색 트리 (Binary Search Tree)
    • 이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성한 트리.
    • 평균 탐색 시간복잡도 => O(logn)
    • 최악 탐색 시간복잡도 => O(n)

 

[참고]

velog.io/@hygoogi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC-8xk66rgt2h

namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

www.leafcats.com/125

blog.naver.com/justkukaro/220618338784

greatzzo.tistory.com/14

www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

velog.io/@dnjscksdn98/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%A5%BC-%EC%99%9C-%EB%B0%B0%EC%9B%8C%EC%95%BC%ED%95%98%EB%8A%94%EA%B0%80

velog.io/@rockjeon/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

en.wikipedia.org/wiki/Binary_search_tree

www.bigocheatsheet.com/