[CS] 배열과 연결 리스트 (Array & Linked List)

자료구조 (Data Structure)

자료구조란 데이터를 저장하고 관리하기 위한 구조를 말합니다. 쉬운 예시로, 약 우리가 도서관에서 셰익스피어의 “햄릿”이라는 책을 찾기 위해서는 도서관에서 분류해둔 카테고리에 따라 [시], [에세이], [소설], [인문] 중 [소설] 카테고리를 선택 후 다시 [한국 소설], [영미 소설], [독일 소설] 등에서 [영미 소설]을 선택합니다. 그리고는 다시 소분류를 타고 타고 내려가 ‘ㅎ’ 영역에 있는 “햄릿”을 찾을 수 있습니다.

이처럼 컴퓨터에도 데이터를 저장할 때 일정한 구조에 맞게 저장하게 되는데 이것을 자료구조라고 하며 컴퓨터 분야에서는 데이터의 효율적인 접근과 조작을 가능하게 해주는 저장 및 관리 방식입니다. 자료구조는 데이터의 특성과 크기, 사용법, 연산, 필요 공간 크기에 따라 여러가지로 나뉩니다.

• 구현에 따른 분류
  • 배열 / 튜플 / 연결 리스트 / 원형 연결 리스트 / 이중 연결 리스트 / 환형 이중 연결 리스트 / 해시 테이블
• 형태에 따른 분류
  • 선형 구조 : 스택 / 큐 / 덱
  • 비선형 구조 : 그래프 / 트리 (이진 트리, 힙)

배열 (Array)

데이터가 많아지게 되면 데이터를 핸들링 할 수 있는 그룹 관리가 필요합니다. 이럴 때 사용하는 것이 배열입니다. 여러 데이터를 하나의 이름으로 그룹핑하여 관리하기 위한 자료구조를 ‘배열’ 이라고 합니다.

배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 정적 자료구조입니다. 배열은 처음 생성될 때 미리 크기를 정해놓게 되며 크기는 동적으로 늘리거나 줄일 수 없습니다. (그러나 자바스크립트의 경우 동적으로 변경이 가능!)

배열은 처음 생성될 때 지정된 크기 만큼의 연속된 메모리 주소를 할당 받게 됩니다. 해당 연속된 메모리 주소 때문에 배열 속 데이터들은 순서를 가지게 되는데, 이러한 순서를 인덱스(index)라고 합니다. 인덱스는 배열에서 가장 중요한 것으로 인덱스를 통해 해당 데이터에 접근할 수 있습니다. 이렇게 인덱스를 알고 있는 경우 배열은 Random Access가 가능하다는 장점이 있습니다. Random Access는 임의 접근이라는 뜻으로 어느 위치에서든 똑같은 속도로 접근이 가능하다는 의미입니다.

배열의 시간 복잡도

• 읽기 (Read)
  
  Random Access를 통해서 특정 위치에 접근할 수 있으므로 배열의 시간 복잡도는 O(1)입니다. 많은 데이터를 읽어야 한다면 자료 구조로 배열을 선택하는 것이 좋습니다.
  

• 검색 (Search)
  
  인덱스를 통해 데이터에 접근하는 것은 용이하지만 해당 데이터의 value는 알지 못합니다. 즉 배열에서 특정 요소를 검색하기 위해서는 순차적으로 모든 데이터를 탐색해서 원하는 value가 나올 때까지 반복해야 합니다. 이렇게 순차적으로 0부터 end까지 데이터를 찾는 방법을 ‘선형 검색(Linear Search)라고 하며, 이렇게 모든 데이터를 탐색해야 하는 경우 시간 복잡도는 O(n)이 됩니다.

• 추가 (Add), 삭제 (Delete)
  
  배열의 처음과 중간에 데이터를 추가하거나 삭제해야 하는 경우에도 시간 복잡도는 O(n)입니다. 왜냐하면 추가하거나 삭제하는 과정에서 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 깨진 배열의 연속적인 특징을 보완해주기 위해 다른 원소들을 밀거나 당겨서 이동시켜줘야 하기 때문입니다.

이러한 부분에 대한 문제점을 해결하기 위한 자료구조가 연결 리스트입니다.

연결 리스트 (Linked List)

연결 리스트는 여러 개의 요소들이 순차적으로 연결된 형태를 갖는 선형 자료구조입니다. 연결 리스트 내의 각 요소를 ‘노드(Node)’ 라고 부르며 가장 첫 번째 노드를 Head, 가장 마지막 노드를 Tail 이라고 칭합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있는데, 이 포인터를 사용하여 원소의 순서를 정하게 됩니다.

연결 리스트는 배열과는 달리 크기를 정할 필요가 없으며 연속된 메모리 주소를 할당받지 않습니다. 크기를 정할 필요가 없다는 것은 메모리가 허용하는 범위 내에서 요소를 제한없이 추가할 수 있는 것을 의미합니다. 그런 의미에서 연결 리스트는 데이터의 삽입과 삭제가 자유로운 장점을 가집니다. 왜냐하면 앞, 뒤에 있는 원소의 포인터만 바꿔주면 되기 때문입니다. 그러나 연속된 메모리 주소를 할당받지 않기 때문에 배열과 같이 임의로 데이터에 접근하는 것이 불가능합니다. 즉 데이터를 탐색해야 할 때 순차적으로 접근해야 하는 단점을 가지고 있습니다.

연결 리스트의 시간 복잡도

• 추가 (Add), 삭제 (Delete)
  
  연결 리스트의 처음과 끝에 요소를 추가하거나 삭제하는 경우 시간 복잡도는 O(1)입니다. 처음과 마지막의 포인터만 수정해주면 되기 때문입니다.

• 읽기 (Read), 검색 (Search)
  
  그러나 연결 리스트의 중간에 요소를 추가하거나 삭제하는 경우의 시간 복잡도는 O(n)입니다. 연결 리스트는 배열과 다르게 연속된 메모리 주소를 할당받지 않기 때문에 특정 요소의 임의 접근하는 Random Access가 불가능합니다. 그래서 처음 노드부터 마지막까지 탐색을 진행해야 하기 때문에 많은 시간이 소요되어 시간 복잡도가 O(n)이 됩니다.

연결 리스트의 종류

연결 리스트에는 단일 연결, 이중 연결, 원형 연결 리스트가 있습니다. 단일 연결 리스트는 단순 연결 리스트라고도 불리는데 하나의 링크 필드를 이용하여 연결됩니다. 마지막 노드는 항상 Null을 가리키게 되고, 선행 노드를 찾기 어렵다는 단점이 있습니다. 선행 노드를 찾기 위해서는 다시 첫 번째 노드부터 탐색해야 합니다. (시간복잡도 O(n))

원형 연결 리스트는 단일 연결 리스트와 비슷한 구조이지만 마지막 노드가 Null을 가리키지 않고 다시 첫 번째 노드인 Head 노드를 가리킵니다. 시간 복잡도에서 설명한 처음과 끝에 노드를 삽입하는 것이 용이하다는 설명이 이럴 때 적용됩니다.

이중 연결 리스트는 하나의 노드에서 선행 노드와 후행 노드를 모두 가리키고 있는 것을 말합니다. 양방향 검색이 가능한 장점이 있지만 공간을 많이 차지하게 되고 코드가 복잡합니다.

배열과 연결 리스트의 차이점

배열 (Array)	연결 리스트 (Linked List)
정적 자료구조	동적 자료구조
메모리 크기가 선언 시점에 정해진다 (javascript 제외)	메모리 크기가 다양하다(node 추가/삭제에 따라 유동적)
연속된 메모리 주소 할당	연속된 메모리 주소를 할당받지 않음.
인덱스(index)	노드(Node) - 데이터, 포인터
접근과 탐색이 편리	추가와 삭제가 편리
빠른 접근 O 많은 데이터 추가/삭제 경우가 적을 때	추가/삭제 O 검색 빈도가 적을 때