자료구조 개념, 종류

자료구조란?

일련의 자료들을 조직하고 구조화 하는 것

ex) 배열, 연결리스트, 트리, ...

 

 

성능 분석

공간 복잡도 - 필요한 공간의 크기

시간 복잡도 - 필요한 실행문의 실행 횟수

 

 

1. 배열 (Array)

   인덱스와 값 <index, value>의 쌍으로 구성된 집합.

   일련의 연속된 메모리 위치로 정의.

 

2. 스택 (Stack)

    LIFO (Last In First Out) : 한쪽 끝(top)에서 모든 삽입과 삭제가 일어나는 list 

 

 

 

 

 

 

3-1. 큐 (Queue)

   FIFO (First In First Out) : 한쪽 끝(rear)에서 삽입이 일어나고 다른 끝(front)에서 삭제가 일어나는 list

3-2. 원형 큐 (Queue)

   front와 rear가 시계방향으로 이동

 

 

4-1. 연결리스트 (Linked List)

   순서 list를 연결 포인터를 사용하여 표현

 

4-2. 원형 리스트 (Circular List)

   단순 연결 리스트에서 마지막 node의 link 필드가 첫 번째 node를 가리킴

   리스트 맨 앞에 새 node 삽입 시, 맨 마지막 node의 link 변경 필요 -> O(n) 소요 (last 있으면 O(1))

 

4-3. 이중 연결 리스트 (Doubly Linked List)

   단순 연결 리스트 단점 보완

   전위 node 접근을 용이하게 하기 위해 양방향 연결 field 가짐