[Data Structure] 꼭 알아야 할 7가지 자료구조

고지훈·2022년 1월 17일
1

LearningRecord

목록 보기
16/17
post-thumbnail

Data Structure(자료구조)

  • 대규모 데이터들을 관리 및 활용에 용이하게 한다.
  • 데이터베이스에서 원하는 데이터를 찾을 수 있게 한다.
  • 사용자가 원하는 또는 프로그램이 필요한 맞춤 알고리즘을 설계할 수 있다.
  • 사용자들의 여러 요청을 한 번에 처리할 수 있다.
  • 데이터 처리 과정을 단순화하면서 처리 속도를 향상시킬 수 있다.

꼭 알아야 할 7가지 자료구조

배열(Array)

배열은 가장 기본적인 자료구조이다. 배열은 생성시 설정된 크기가 고정되고, 각 셀에는 인덱스 번호가 부여된다. 배열을 활용 시 부여된 인덱스를 통해 해당 셀 안에 있는 데이터에 접근할 수 있다.

[시간 복잡도]

자료구조가져오기(값)추가하기삭제하기
배열(Array)O(n)O(n)O(n)

[장점]

  • 바로 만들어서 활용하기 쉽다.
  • 더 복잡한 자료구조의 기초가 될 수 있다.
  • 원하는 데이터를 효율적으로 탐색/가져올 수 있다.
  • 정렬에 용이하다.

[단점]

  • 데이터를 저장할 수 있는 메모리 크기가 고정되어있다.
  • 데이터 추가/삭제 방법이 비효율적이다.
  • 구조 재구성 시 정렬하는 방식이 비효율적이다.

스택(Stack)

스택은 순서가 보존되는 선형 데이터 구조 유형이다. 가장 마지막 요소부터 처리하는 LIFO(Last In First Out)특성을 갖고있다. 스택은 쌓여있는 접시 더미와 같이 동작한다. 새로운 접시가 쌓일때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가져가는 것과 같다.

[시간 복잡도]

자료구조가져오기(값)추가하기삭제하기
스택(Stack)O(n)O(1)O(1)

[장점]

  • 동적인 메모리 크기
  • 데이터를 받는 순서대로 정렬된다.
  • 빠른 런타임

[단점]

  • 한 번에 하나의 데이터만 처리가능하다.

큐(Queue)

큐는 스택과 비슷하지만 가장 먼저 입력된 요소를 처리하는 FIFO(First In First Out)특성을 갖고있다. 큐는 놀이공원에서 서는 줄과 같이 동작한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다.

[시간 복잡도]

자료구조가져오기(값)추가하기삭제하기
큐(Queue)O(n)O(1)O(1)

[장점]

  • 동적인 메모리 크기
  • 데이터를 받는 순서대로 정렬된다.
  • 빠른 런타임

[단점]

  • 가장 오래된 요소만 가져온다.
  • 한번에 하나의 데이터만 처리 가능하다.

연결 리스트(Linked list)

연결리스트는 데이터의 물리적 배치를 사용하지 않는 구조이다. 각 요소는 노드라는 것에 저장되는데 다음 노드 연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장된다. 모든 노드가 연결될때 까지 반복이 되어 노드의 연결로 이루어진 자료구조다.

연결 리스트에는 단일 연결 리스트, 이중 연결 리스트가 있다.

[시간 복잡도]

자료구조가져오기(값)추가하기삭제하기
연결리스트(Linked list)O(n)O(1)O(1)

[장점]

  • 새로운 요소들의 추가 및 삭제가 용이하고 효율적이다.
  • 배열처럼 메모리에 연속적으로 위치하지 않는다.
  • 배열처럼 구조의 재구성이 필요없다.
  • 동적인 메모리 크기
  • 메모리를 더 효율적으로 쓸 수 있기 때문에 대용량 데이터 처리에 적합하다.

[단점]

  • 배열보다 메모리를 더 사용한다.
  • 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 검색한다.
  • 노드를 반대 방향으로 검색할 때 비효율적이다. (이중 연결 리스트의 경우)

해시 테이블(Hash table)

해시 테이블은 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터구조이다. 이 데이터 구조는 테이블 내에 더 작은 서브그룹인 버킷에 키와 값의 쌍을 저장한다. 해시 테이블은 키를 저장할 때 메모리 공간을 덜 사용할 수 있도록 키를 해시 함수를 통해 해시라는 특정 숫자값으로 변환한다. 해시 테이블은 필요할 때만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

키는 검색 시 사용되는 문자열이고 값은 해당 키와 쌍을 이룬 데이터다. 검색된 각 키는 미리 정의된 해시함수를 통해 해시값을 받고 버킷을 가리킨다. 해시 숫자는 버킷의 인덱스를 의미한다. 버킷에서 검색할 때 입력된 키를 찾고 해당 키와 관련된 값을 반환한다.

[시간 복잡도]

자료구조가져오기(값)추가하기삭제하기
해시테이블(Hash Table)O(1)O(1)O(1)

[장점]

  • 새로운 요소들의 추가, 삭제가 용이하고 효율적이다.
  • 원하는 값의 검색/가져오기가 빠르고 효율적이다.
  • 동적인 메모리 크기

[단점]

  • 충돌이 일어날 수 있다. (입력된 키의 해시 값이 이미 데이터가 저장된 버킷을 가리킬 수 있다.)
  • 충돌이 자주 일어날 수 있으며 해시함수의 정비가 필요한 경우가 많다.

그래프(Graph)

그래프틑 노드 사이에 엣지가 있는 자료구조이다. 그래프는 방향이 있을 수 있고 없을 수도 있다. 그래프로 구조를 어떻게 설계 그리고 무엇을 하고 싶냐에 따라 시간복잡도가 달라진다.

[시간 복잡도]

자료구조가져오기(값)노드/엣지 추가하기노드 삭제하기엣지 삭제하기
그래프(Graph)O(N+E)O(1)O(N+E)O(E)

[장점]

  • 새로운 요소들의 추가/삭제가 용이하고 효율적이다.
  • 구조의 응용이 가능하다.

[단점]

  • 충돌이 발생할 수 있다.
profile
"계획에 따르기보다 변화에 대응하기를"

0개의 댓글