[자료구조] 자료구조를 알아야하는 이유와 배열(list), 연결리스트(linked list)

 배열 포스팅을 쓰면서 참조, mutable, id까지 쓰려다가 평생 포스팅 못 할 것 같아 일단 간단하게 자료구조에 대한 글 먼저 쓰려고 한다.

 

자료구조 (Data Structure)

 자료구조는 컴퓨터에서 값을 담는 구조이다. 컴퓨터는 자료구조로 값 사이의 논리적 관계를 조직화한다. 예를 들어 값 사이의 계층을 만든다던가, 값의 순서를 인식한다던가 하는 것이다. 이런 논리적 관계의 인식 때문에 각 자료구조는 같은 값을 담아도 컴퓨터 내에서 사용하는 메모리의 용량과, 값을 삽입, 수정, 탐색, 삭제 시 소요하는 시간이 달라진다. 시간과 메모리는 프로그램의 가장 기본적인 비용이며, 이것이 개발자가 자료구조를 알아야하는 이유이자 알고리즘을 배울 때 자료구조가 항상 따라오는 이유이다.

 

 컴퓨터의 기본 자료구조는 배열, 연결 리스트, 큐, 스택, 힙, 해쉬테이블, 트리, 그래프로 나뉜다. 여기서 뒤의 두 자료구조는 계층을 가질 수 있는 비선형 자료구조이며, 나머지는 선형 자료구조이다.

 

배열 (Array)

 배열은 자료구조들 중 가장 기본이 되는 자료구조이다. 정의는 여러개의 데이터를 하나의 변수로 모아놓은 집합체이며, 컴퓨터에 저장될 때 연속적인 메모리를 할당받기 때문에, 연속된 메모리 주소의 집합이라고도 생각한다.

 

  배열의 가장 큰 특징은 논리적 순서와 물리적 순서, 즉 배열이 표시되는 순서와 실제 컴퓨터에 저장되는 기억공간의 순서가 같다는 것이다. 즉, 하나의 인덱스와 값이 쌍으로 저장된다는 것이다. 배열에서 값은 원소(element)라고 부르므로, 배열은 (인덱스:값)의 집합체라고도 할 수 있다.

배열 int A[4]의 논리적 표현

배열 int A[4]의 물리적 표현

 인덱스를 갖는다는 것은 인덱스를 통한 값의 접근이 가능하다는 뜻이며, 이는 값에 순차적으로 접근할 필요 없이 인덱스를 통해 바로 접근할 수 있다는 장점을 갖는다 ("세 번째 원소"). 따라서 원소가 어디에 저장되어있든, 각 원소에 대한 접근 시간이 동일하다. 하지만 순서대로 저장된다는 것은 반대로 삭제나 삽입시 순서가 수정되어야한다는 것을 뜻하므로, 삽입, 삭제에 원소 이동에 따른 추가 비용이 발생한다는 단점이 있다.

 

 예를 들어, {1,2,3} 이라는 집합이 순서를 가지지 않고, 4라는 값을 집어넣는다면 그냥 아무데나 집어넣으면 되겠지만, "두 번째"에 집어넣어야한다면 2의 위치에 4를 집어넣고, 2,3을 뒤로 한 칸씩 밀어주는 작업이 필요하다. 반대로 삭제시에는 삭제한 원소를 뺀 후 뒤에 있는 원소들을 한 칸씩 앞으로 옮겨주는 작업이 필요하다.

"두 번째" 공간, 그리고 2와 3의 순서를 지키기 위해 2,3 원소 이동 비용 발생

 

 

  이런 단점은 삽입, 삭제가 빈번히 일어나는 알고리즘이나 이동해야하는 데이터가 굉장히 많은 경우 시간 낭비가 크다는 문제를 발생시키기 때문에, 배열을 사용할 때는 이 점을 고려해야한다.

 

연결리스트 (linked list)

연결리스트에는 다음과 같은 용어가 사용된다.

• Node: 연결리스트의 각 원소(element)
  • Head node: 연결리스트의 맨 앞에 있는 노드. 첫 번째 값을 담은 노드의 주소값을 가리킨다.
  • Tail node: 연결리스트의 맨 끝 노드. 원형리스트가 아니면 Tail  node의 참조값은 None이다.
  • Predecessor node: 현재 주목하고 있는 노드의 바로 앞 노드
  • Successor node: 현재 주목하고 있는 노드의 바로 뒷 노드
• Pointer/ Link: 각 뒷 노드를 가리키는(참조하는) 정보를 담는 곳 (메모리 주소값을 담음)
• Data: 값을 담는 곳

 

 연결리스트는 배열의 단점을 어느 정도 해소한 자료구조이다. 논리적으로는 자료가 순서를 가지지만, 물리적으로는 (컴퓨터에 실제 저장될 때는) 주소 공간의 임의의 위치에나 저장된다. 단, 순서를 기억하기 위해 다음 값의 메모리 주소를 함께 저장한다. 연결리스트에서는 이를 앞 노드가 뒷 노드를 "참조한다"라고 표현한다.

 

 이를 통해 값을 삽입할 때 임의의 공간에 값을 저장할 수 있게 되며, 삽입 시 다음 값의 메모리 주소를 함께 저장하기만 하면 추가 작업 없이 배열의 순서가 그대로 유지될 수 있다. 삭제 역시, 삭제하고자하는 노드의 앞 노드가 참조하는 메모리 주소 값을 뒷 노드의 주소값으로 바꿔주기만 하면 되므로, 배열과 달리 데이터의 크기에 영향을 받지 않는다. 예를 들어, 위 그림에서 두 번째 요소를 삭제한다면, 1이 참조하는 값을 62에서 50으로 바꿔주기만 하면 된다. 두 번째 요소 뒤에 저장되어 있는 요소가 몇 개든 작업 시간은 동일하다.

 하지만 값에 접근할 수 있는 인덱스가 없으므로, 즉, n번째 값이 어디에 저장되어 있는지 모르므로, 특정 노드에 접근하기 위해서는 순차적으로 접근해야하는 단점이 있다. 배열에서는 A리스트 세 번째 요소에 접근하기 위해서 A[3]으로 접근할 수 있지만, 연결 리스트에서는 첫 번째 노드가 참조하는 값을 찾아 두 번째 노드로 이동하고, 두 번째 노드가 참조하는 값을 찾아야지만 세 번째 노드로 이동할 수 있는 것이다.

 

 결론적으로 배열은 삽입, 삭제가 빈번한 알고리즘에, 연결리스트는 탐색이 빈번한 알고리즘에 적합하지 않을 수 있다.

 

연결리스트의 종류

 

• 단일 연결리스트 (Singly linked list) : 링크 필드가 하나만 있는 가장 단순한 구조. 뒤에서 앞으로 이동할 수 없다.
• 단일 원형 연결리스트 (Circular singly linked list): 링크 필드가 하나만 있지만 맨 끝 노드가 맨 앞 노드를 참조하여 맨 뒤에서 맨 앞으로 찾아갈 수 있다.
• 이중 연결리스트 (Doubly linked list): 링크 필드가 두 개 있는 구조로 앞 뒷 노드가 서로 참조하여 뒤에서 앞으로 이동할 수 있다.
• 이중 원형 연결리스트 (Circular doubly linked list): 링크 필드가 두 개 있고, 맨 끝 노드가 맨 앞 노드를 참조하여 각 노드에서 앞 뒤로도, 맨 뒤에서 맨 앞으로도 이동할 수 있다.

 

 이렇게 여러 종류가 있긴 한데, 아직까지 코테에서 단일 연결리스트 외의 다른 종류를 본 적은 없다.

구현은 다음 이시간에..