[자료구조] 배열, 연결리스트

선형 자료구조란?

선형 자료구조란, 자료를 순차적으로 나열한 형태의 자료구조를 말한다. 대표적으로 배열, 연결 리스트(Linked List), 스택, 큐등이 있으며 하나의 자료가 있으면 그 뒤에 다른 하나의 자료가 존재하는 구조이다. 이에 반대되는 개념으로 비선형자료구조가 있는데, 비선형자료구조란 말그래도 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태라고 볼수 있다. 이에 대한 예시로는 트리, 그래프가 대표적이다.

이번 글에서는 선형자료 중, 배열과 연결 리스트에 대해서 알아보도록 하겠다.

정적 배열 (Static array)

• 맨 처음 선언 시, 해당 배열의 크기를 지정하고, 한번 지정된 크기는 절대 변경할 수 없다
• 배열에 저장된 자료들은 메모리 상에서 연속적으로 위치한다.
  • 임의 접근(Random Access)에 용이하다.
    
    ex) 정수형 자료 10개를 담을 수 있는 배열을 선언한다고 가정해보겠다. 그러면 메모리에 4byte * 10인 40byte의 공간이 할당되고, 이 공간에 정수들이 채워지게 된다. 이 선언한 배열은 배열이 시작되는 지점의 메모리주소에 대한 정보를 가지고있고, 만약 4번째 자료에 접근하고 싶다면, 해당 주소에서 4칸 떨어진 곳의 자료를 가지고 오면된다. 이 과정이 결국 주소에 4칸의 값을 더해서 그 위치로 접근 하는 것 이므로, 1번째 자료에 접근하든, 4번째 자료에 접근하든 비용의 차이가 존재하지 않는다.
    
    *임의접근 : 접근하고자 하는 데이터가 어디에 위치하건, 첫번째에 있는 데이터와 N번째에 있는 데이터를 접근하는데 드는 비용이 같다.
    
    
    
    

동적 배열 (Dynamic array)

• 배열과 동일한 구조적 특성을 가진다.
  • 임의 접근(Random Access)에 용이하다.
• 일반 배열은 지정된 크기를 변경할 수 없지만, 동적배열은 배열 크기의 변경이 가능하다.
  • 현재 지정된 배열의 크기가 다 찼을 때, 뒤에 새로운 자료를 추가하게 되면, 현재 차지하고 있는 공간보다 더 큰 새로운 공간을 할당받고 그 위치에 원래 있던 자료들을 다 옮기고 그 뒤에 새로운 자료를 추가하는 원리이다.
    
    ex) C++의 stl에서 제공하는 동적배열 자료구조인 vector를 기준으로 살펴보면, 해당 배열에 자료가 다 찼을 경우, 현재 크기의 1.5배정도 되는 크기의 공간을 새로 할당받고, 그 곳으로 자료를 옮기게 된다. 예를 들어, 10칸의 배열이 꽉찬 상태에서, 11번째 자료를 넣고싶다면, 10칸의 1.5배인 15칸짜리의 배열을 새로 만들고, 그 곳으로 자료를 옮기고 11번째에 자료를 넣는 것이다.
    
    
  • 다만 배열의 크기를 늘리는 과정에서 자료들은 옮기는 일에서 비용이 발생하므로, 어느정도 자료의 수가 예측이 된다면, 미리 공간을 그만큼 지정하는 것이 좋다.
• 중간 원소의 삽입/삭제에 불리하다.
  • 만약 배열에서 중간에 있는 원소를 삭제하면 자료들은 연속적으로 존재해야하므로 삭제한 원소 뒤에 있는 원소들을 한칸 씩 땡겨와야한다. 또한 중간에 원소를 삽입하고 싶다면, 뒤에 있는 원소들을 한칸씩 뒤로 밀고, 그 공간에 원소를 삽입해야한다
    
    ex) 만약 100개의 원소가 있는 배열에서 50번째 원소를 삭제하고 싶다면, 첫번째 원소를 삭제하고 나머지 50개의 원소를 앞으로 땡겨야 하는 것이다. 그런데 이것이 극단적인 예로 1억개의 원소가 있다고 했을때, 가운데의 원소를 삭제하거나 삽입하는 것은 굉장히 비효율적이라는 것을 알 수 있다.

배열의 시간 복잡도 계산

자료의 접근, 삽입/삭제의 시간 복잡도를 계산해보겠다.

1. 접근 ➡ O(1)
   자료마다 index를 부여해놓았으므로(순차적으로 저장되어 있으므로 몇번째 원소인지 알기쉬움), 자료에 접근할 때, 그 index로 바로 접근을 하면 되기 때문에 시간 복잡도는 O(1)이다.
2. 삽입/삭제 ➡ O(n)
   위에서 설명하였 듯, 가운데에 있는 자료를 삭제하고 한다면, 그 삭제된 공간을 매워 자료의 연속성을 유지하여야 하므로 삭제한 자료 뒤에 있는 자료들을 한 칸씩 앞으로 땡겨오는 작업이 필요하다. 이것이 결국 n번 이루어지므로 시간 복잡도는 O(n)이다. 자료를 삽입 하는 경우도 마찬가지 이다.
   
   
   
   

연결 리스트 (Linked List)

연결 리스트는 앞서 살펴본 배열과는 다르게 자료들이 연속적으로 있지않다. 자료들은 메모리 이곳저곳에 산포해있고, 자료들은 자신의 앞에 있는 자료와 뒤에 있는 자료의 위치를 저장하고 있다.

• 배열의 장점이었던 임의접근이 불가능하다. ⬅ 원하는 값에 접근하려면 앞에서 부터 타고타고 가야하므로 비효율적이다.
  
  ex) 만약 5번째 원소에 접근하고 싶다면, 그 자료의 위치는 4번째 원소와 6번째 원소만이 가지고 있다. 그래서 4번째 자료에 접근하려고 보니 또 4번째 원소의 위치는 3번째 원소만이 가지고 있다. 이렇게 5번째 원소에 접근하기 위해서 1번째 원소부터 타고타고 들어가야 하므로 임의접근이 불가능하여 N번째 원소를 바로 찾을 수 없다는 단점이 있다.
  
  
• 이러한 구조는 배열의 단점이었던 원소의 중간 삽입/삭제에 있어서 탁월한 성능을 보인다.❗ 말그대로 삽입, 삭제의 연산이 빠른거지, n번째 자리를 찾아서 그 자리에 있는 원소를 삭제하거나 아니면 그자리에 원소를 삽입하는 것은 n번째 자리를 찾는 다는 연산이 포함되어 있으므로 비효율적일 수 있다.
  
  ex) 5번째 자료를 삭제하고 싶다면 그냥 4번째 원소와 5번째 원소의 연결을 끊어버리고 4번째 원소를 6번째 원소와 이어버리면된다. 따라서 배열에서 원소를 삭제할 때 나머지 원소를 한칸씩 땡기던 소요가 큰 일을 하지 않아도 되므로 굉장히 빠르게 중간에 있는 원소를 삭제하거나 삽입할 수 있다.

 

 

연결 리스트의 시간 복잡도 계산

자료의 접근, 삽입/삭제의 시간 복잡도를 계산해보겠다.

1. 접근 ➡ O(n)
   N번째 자료에 접근하려면 N-1번째 자료에서 정보를 얻어와야하고, N-1번쨰는 또 N-2번째로 부터 얻어와야하고, 결 국 반복되면 1번째 자료부터 타고타고 가야하므로 시간복잡도는 O(n)이 된다.
   
   
2. 삽입/삭제 ➡ O(1)
   삽입/삭제는 해당 위치의 자료가 가지고 있는 레퍼런스만 바꾸어 주면되므로 시간복잡도는 O(1)이라고 볼 수 있다.

 사실우리가 선형자료구조를 사용하고자 할때, 대다수는 연결리스트가 아닌 배열을 사용할 것이다. 배열이 가지는 이점이 훨씬 크기때문이다. 하지만 그럼에도 리스트를 공부하는 이유는 뒤에나올 노드를 사용하는 다른 자료구조들의 기초적 지식을 얻을 수 있기때문이다.