자료구조와 알고리즘

Inflearn_study_03

자료구조

배열

배열은 연속적인 할당 구조이다. 운영체제는 배열의 시작 주소만 가지고 있고 특정 인덱스 참조를 한다면 시작주소에서 일정 크기 떨어진 주소의 값을 불러온다.

연결 리스트에 비해 참조에 더 유리하다.

연결 리스트

분산된 데이터를 서로 연결해주는 자료구조이다.

데이터와 다음의 주소값을 저장한 뒤 처음 노드값을 기준으로 연결된 값을 불러온다.

배열에 비해 삽입과 삭제가 자주 일어난다면 더 유리한 자료구조 이다.

스택

LIFO, FILO 자료구조로 나중에 들어온 데이터가 처음으로 사용된다면 그 자료구조는 스택으로 볼 수 있다.

큐

FIFO 자료구조로 먼저 들어온 데이터가 먼저 사용된다. 단 tail을 가리킬 때 O(n)의 시간복잡도를 가지므로 싱글 연결 리스트에 비해 더블 연결 리스트로 활용하여 큐를 구현하면 각 노드가 이전과 다음을 가리키면 더 좋은 구현을 할 수 있다.

덱

데이터의 삽입과 조회 삭제를 양방향에서 하는 자료구조이다. 스택과 큐가 혼합된 자료구조이다.

해시 테이블

데이터의 해시함수값을 통해 테이블의 인덱스를 설정하여 O(1)으로 삽입과 조회를 하는 자료구조이다. 해시 충돌이 일어난다면 해당 인덱스를 연결 리스트를 활용하여 같은 인덱스에 저장한다.

셋

해시 함수의 값에 따라 데이터의 중복을 허용하지 않는 자료구조이다. 해시 테이블과 다르게 키만 사용하고 키 값 그 자체가 밸류가 된다.