자료구조란? - 선형 자료구조

자료구조란?

위키백과에 따르면, 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미하며, 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다고 합니다.

목적에 맞게 사용한 자료구조는 실행시간을 단축시키고 메모리 용량을 절감시키는 등 보다 좋은 성능을 기대할 수 있습니다.

선형 자료구조란?

선형 자료구조는 데이터가 연속적으로 연결되어 있는 모양으로 구성하는 방법입니다.

선형의 사전적 의미는 선처럼 가늘고 긴 모양입니다. 그렇다면, 선형 자료구조는 데이터가 선처럼 이어져 있다고 생각해도 좋을 것 같습니다.

즉, 데이터가 2차원적으로 일직선상에 놓여있다고 볼 수 있습니다.

예를 들어서, 꼬리잡기 놀이처럼 머리부터 꼬리까지 한직선으로 되어있는것과 같습니다.

배열

특징

많은 수의 데이터를 다룰 때 사용하는 자료구조로 각 데이터를 인덱스와 1:1 대응하도록 구성되어 있습니다.

장점

• 인덱스를 이용하여 데이터에 빠르게 접근 가능

단점

• 데이터의 추가, 삭제가 번거로운 편입니다.
  • 추가, 삭제할 때마다 새로운 배열을 만들어서 최대길이를 추가, 삭제에 맞춰서 설정하고 새로운 배열에 데이트 초기화하는 과정이 필요

 

연결리스트

특징

처음에 접하게 되면 굉장히 혼란스러운 자료구조이지만, 배우고 나면 가장 매력적인 자료구조라고 생각됩니다! 저는 그렇습니다 허허허

연결리스트는 데이터를 링크로 연결해서 관리하는 자료구조이며, 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되어 있지 않습니다.

예를 들어서 드라마 속에서 종종 비밀집단이 있는데 보스의 얼굴은 이인자만 알고 이인자의 얼굴은 3인자만 알고 이런 식으로 한 사람의 정보를 다른 사람이 갖고 있는 비밀집단과 같은 구조라고 보면 좋을 것 같습니다.

장점

• 데이터 공간을 미리 할당할 필요 없습니다.
• 리스트의 길이가 가변적으로 데이터 추가, 삭제 용이

단점

• 연결구조를 위한 별도 데이터 공간 필요
• 데이터를 찾는 시간이 상대적으로 느림
• 데이터 추가, 삭제 시 데이터의 연결을 재구성해야 하는 작업이 필요합니다.

스택

특징

후입선출(LIFO)의 구조로, 마지막에 들어온 데이터가 먼저 나가는 자료구조입니다.

예를 들어서 함수 콜 스택 등이 있으며, 깊이 우선 탐색(DFS) 등등 여러 곳에서 사용됩니다.

큐

특징

선입선출(FIFO)의 구조로, 먼저 들어온 데이터가 먼저 나가는 구조입니다.

예를 들어서 프린터 출력, 너비 우선 탐색(BFS) 등등 여러 곳에서 사용됩니다.

• Enqueue: 큐에 데이터 추가하는 것을 의미합니다.
• Dequeue: 큐에서 데이터를 꺼내는 것을 의미합니다.

데크

특징

양쪽에서 삽입과 삭제가 모두 가능한 자료구조이며, Stack과 Queue를 합친 형태입니다.

해시 테이블

특징

키(key), 값(value)을 대응시켜 저장하는 데이터 구조입니다. 평균 O(1)의 시간 복잡도를 갖지만 해시 충돌이 일어난다면 최악의 시간 복잡도는 O(N)이 됩니다.

• 키: 해시 테이블 접근을 위한 입력값
• 해싱: 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
• 해시 함수: 키를 해시 값으로 매핑하는 연산
• 해시 값: 해시 테이블의 인덱스
• 해시 테이블: 키 - 값을 연관시켜 저장하는 데이터 구조

해시 테이블에서는 해시 충돌이라고 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 문제가 발생하는데, 이를 해결하기 위한 방법으로 개방 주소법과 분리 연결법이 있습니다.

장점

• Key를 이용하여 데이터를 탐색하기 때문에 해시 충돌이 없는

단점

• 데이터의 순서를 보장하지 않아 정렬이나 순차적인 메모리 저장이 필요한 경우 부적합
• 해시 충돌로 인해 시간 복잡도가 커질 수 있음