선형 자료구조

자료구조

---

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

 

 

 

 

선형 자료구조

---

 

자료가 선형으로 저장되어 있는 자료구조입니다.

선형 자료구조의 종류는 다음과 같습니다.

 

배열

메모리의 연속적인 공간을 차지하는 자료구조입니다.

배열은 정적 배열과 동적 배열로 나누어집니다.

 

• 정적 배열
  • 초기화와 동시에 크기가 결정되고 메모리의 스택 영역에 저장됩니다. 일반적으로 선언하는 배열은 정적 배열입니다.
• 동적 배열
  • 런타임시 크기가 동적으로 정해지고 메모리의 힙 영역에 저장됩니다. 대표적으로 C와 C++에서 동적할당을 통해 배열을 생성하면 그것이 동적 배열입니다.

 

• 시간복잡도
  • 검색: O(1)
    • 인덱스로 접근가능하기 때문에 매우 빠릅니다.
  • 삽입, 삭제: O(n)
    • 배열의 5번째 위치에 삽입을 하고 싶다면 원래 5번째 위치에 있던 데이터는 6번째로, 6번째 위치에 있던 7번째로 이동시켜야 하기 때문입니다. 삭제의 경우도 마찬가지입니다.
    • 하지만 배열의 맨 마지막 위치에 삽입, 삭제를 하고 싶다면 시간 복잡도는 O(1)입니다.

 

리스트

자료가 순서대로 연결되어 있는 자료구조입니다.

배열과 다르게 동적으로 크기가 할당되고 불연속적인 메모리 공간을 점유합니다. 대신 포인터를 사용하여 다음 값의 주소를 가리켜 자료끼리 연결되어 있습니다.

예외로 C#과 Python에서 리스트는 동적 배열의 특성을 가집니다. 이렇듯 언어마다 자료구조의 정의가 다를 수 있습니다.

 

• 시간복잡도
  • 검색: O(n)
    • 연결리스트의 경우 포인터를 통해 순차적으로 접근해야 하므로 O(n)의 시간이 걸립니다. 하지만 동적 배열 형태의 리스트는 인덱스로 접근이 가능하여 이 경우 O(1)의 시간이 걸립니다.
  • 삽입, 삭제: O(1)
    • 포인터의 위치만 변경하면 되기 때문에 빠릅니다. 5번째 위치에 삽입하고 싶다면 4번째 데이터의 포인터가 가리키는 것을 새롭게 삽입하는 데이터로 바꾸고 해당 데이터의 포인터의 방향을 원래 5번째 위치에 있던 데이터로 바꿔주면 됩니다.
    • 삽입해야 할 위치를 모른다면 검색의 비용이 추가로 듭니다.

 

스택

LIFO 성질을 가진 자료 구조입니다. LIFO(Last In First Out)이란 가장 나중에 들어간 것이 먼저 나온다는 뜻입니다.

인터넷 방문기록이 그 예시입니다. 뒤로 가기 버튼을 누르면 가장 나중에(최근에) 방문했던 인터넷 창이 나옵니다.

 

• 시간복잡도
  • 검색: O(n)
    • 원하는 노드를 찾을 때까지 삭제해야 합니다.
  • 삽입, 삭제: O(1)
    • 중간에 삽입, 삭제할 수 없습니다. 항상 삽입한 순서대로 저장되고 삭제할 때는 가장 나중에 들어간 데이터가 삭제됩니다.

 

큐

FIFO 성질을 가진 자료 구조입니다. FIFO(Fast In First Out)이란 가장 먼저 들어간 것이 먼저 나온다는 뜻입니다.

쉽게 설명해 드리면 사람들이 줄서는 방식입니다. 가장 먼저 온 사람이 가장 일찍 들어가죠? 

 

• 시간복잡도
  • 검색: O(n)
    • 스택과 마찬가지로 원하는 노드를 찾을 때까지 삭제해야 합니다.
  • 삽입, 삭제: O(1)
    • 역시 중간에 삽입, 삭제할 수 없습니다. 항상 삽입한 순서대로 저장되고 삭제할 때는 가장 먼저 들어간 데이터가 삭제됩니다.