[Data Structure] 자료구조 - 1 (배열, 스택, 큐, 연결 리스트)

배열 (Array)

- 메모리를 미리 확보하여 데이터 공간을 생성함

- 선언한 크기 이상으로 확장이 어려움

- 각 셀에는 인덱스 번호가 부여되며, 인덱스 번호 기준으로 데이터의 수정이 이루어짐

- 데이터 조회, 정렬에 용이한 구조

 

 

스택 (Stack)

- 메모리를 동적으로 할당하여 데이터 공간을 생성함

- FILO(First In Last Out) 메커니즘으로 동작함

 

* FILO(First In Last Out) : 처음에 넣은 데이터는 가장 마지막에 조회할 수 있다는 것을 의미하며, 필요할 때 마다 위에서부터 접시를 하나씩 빼서 쓰는 것과 같은 원리임

 

※ 아래 사진은 스택에 데이터 A, B 가 이미 들어있다고 가정하고 각 순서에 맞게 데이터를 PUSH, POP 한 경우임

최종 출력 순서는 가장 마지막에 들어온 데이터 C, 그 다음 데이터 B, 데이터 A 순이다.

스택 자료조회 예시

 

큐 (Queue)

- 메모리를 동적으로 할당하여 데이터 공간을 생성함

- FIFO(First In First Out) 메커니즘으로 동작함

- 스택(Stack) 과 유사한 구조

 

※ 입출력이 한 곳인 스택과 다르게 큐는 양 끝에서 이뤄지며 한 쪽은 입력, 다른 한쪽은 출력 전용으로 사용한다.

스택 - 들어가는 문과 나가는 문이 같음

큐 - 들어가는 문, 나가는 문이 따로 존재함

좌) 스택(Stack) 우) 큐(Queue)

 

연결 리스트 (Linked List)

- 각 노드는 데이터와 *포인터(Pointer)로 구성됨

- 포인터(Pointer)는 다음으로 조회할 노드의 주소값을 담고 있음

- 단일(Single), 이중(Double), 원형(Circular) 연결리스트 3가지의 형태가 존재함

- 필요에 따라 노드의 추가, 삭제가 용이함

- 배열에 비해 더 많은 공간을 차지함(포인터의 유˙무 차이)

 

* 포인터(Pointer) : 메모리의 주소값을 저장한 변수

단일 연결 리스트

 

이중 연결 리스트

 

원형 연결 리스트

 

자료구조별 효율성을 나타낸 차트

[3] 자료구조별 효율성. Complexity_Cheatsheet.

 

궁금한 것

Q1. 기존 배열의 형태를 유지한 채 추가적인 공간할당이 필요하다면, 끝 인덱스의 값에 포인트를 넣어 다른 배열을 지정하는게 가능한가? (배열 + 연결 리스트의 형태)

 

 

# Referrence

[1] https://velog.io/@jha0402/Data-structure-개발자라면-꼭-알아야-할-7가지-자료구조

[2] https://ko.wikipedia.org/wiki/연결_리스트

[3] 자료구조별 효율성. Complexity_Cheatsheet.

  URL : http://souravsengupta.com/cds2016/lectures/Complexity_Cheatsheet.pdf