자료구조 - 배열과 리스트

배열(Array)

---

배열

- 배열은 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.

- 배열은 인덱스를 통해 값을 바로 접근할 수 있다.

- 배열의 단점으로는 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.

- 위의 사진처럼 6이라는 값은 3과 4 사이에 삽입하려면 4와 5를 한 칸씩 뒤로 옮겨야 된다. 만약 배열의 길이가 1,000,000 정도 된다면 하나의 값을 삽입하기 위해서 많은 양의 데이터를 움직여야 하는 단점이 있다.

- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.

- 구조가 간단하므로 코딩 테스트에서 제일 많이 사용된다.

 

리스트(List)

---

리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 선형 자료구조이다.

리스트

리스트는 배열과 달리 데이터가 인접한 위치에 저장되는 것이 아닌 포인터를 통해서 다음 요소를 가리켜서 연결된 구조이다.

위에서 알아본 배열과 리스트는 비슷하면서도 많이 다른데 어떤 장단점이 있는지 알아보자.

 

리스트의 장점

1. 동적인 데이터 구조

배열은 메모리에서 연속된 위치에 저장되야 하지만 리스트는 각 노드가 임의의 위치에 저장된다. 따라서 배열과 다르게 리스트는 데이터 구조의 크기를 동적으로 할당할 수 있다.

 

2. 메모리 효율성

동적인 데이터 구조를 가지고 있어서 요구 사항에 맞게 크기가 증가하거나 감소할 수 있어 메모리 낭비를 방지할 수 있다. 

 

3. 삽입 및 삭제의 용이성

배열에서 삽입과 삭제를 할 때는 데이터를 이동시켜야 되지만 리스트는 포인터를 활용하여 데이터의 주소만 변경해주면 되기 때문에 삽입과 삭제가 빈번한 작업일 수록 배열보다 유리하다.

 

4. 다양한 자료구조, 알고리즘에서 구현

스택, 큐, 그래프, 해시 맵 등 다양한 데이터 구조와 알고리즘에서 사용될 수 있다.

 

리스트의 단점

1. 메모리 사용량

리스트를 사용하기 위해서는 각 노드를 연결할 포인터가 추가적으로 필요하기 때문에 메모리를 추가적으로 요구된다.

 

2. 느린 데이터 접근

원하는 데이터를 찾고자 할 때 배열은 인덱스를 통해서 바로 접근이 가능하지만 리스트는 노드를 하나씩 순회하면서 찾아야 되기 때문에 느리다.

앞서 장점에서 설명했던 것처럼 배열은 메모리에 연속되는 위치로 데이터가 저장되는데 그로 인하여 인덱스로 빠르게 접근이 가능하다. 반면에 리스트는 임의의 위치에 각 노드가 저장되는 구조로 어느 주소에 해당 노드가 있는지는 이전 노드를 통해서 확인해야 되기 때문에 인덱스로 접근이 불가하다.

 

리스트는 3개의 종류로 구분된다.

1. 단일 연결 리스트

2. 이중 연결 리스트

3. 원형 연결 리스트

 

단일 연결 리스트

---

단일 연결 리스트

단일 연결 리스트는 여러 연결 리스트 중에서 가장 간단한 유형으로 모든 노드가 동일한 데이터 유형을 가진 다음 노드에 대한 포인터를 포함한다.

하나의 노드에는 다음에 위치할 노드의 주소만 가질 수 있어 데이터를 순회할 시 한 방향으로만 할 수 있다.

 

 

이중 연결 리스트

---

이중 연결 리스트

이중 연결 리스트는 한 노드가 다음 노드의 주소만 가지고 있는 것이 아닌 이전 노드의 주소도 가지고 있는 구조이다.

단일 연결 리스트 보다 삽입 삭제가 비교적 더 자유롭다는 장점을 지니고 있다.

그림을 통해서 살펴보면 4라는 데이터를 2와 3사이에 삽입한다고 가정했을 때 이전의 단일 연결 리스트에서는 2번 노드의 next가 4번을 가리키게 하고, 4번의 next가 3번 데이터를 가리키게 변경을 해줘야 한다.

이중 연결 리스트는 4번 노드의 prev를 2번 노드의 next와 연결시켜주고, 4번 노드의 next를 3번 노드의 prev와 연결시켜주면 되서 삽입 및 삭제가 조금 더 유연하다.

 

 

원형 연결 리스트

---

원형 연결 리스트

원형 연결 리스트는 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 구조이다.

그림을 보면 원형 연길 리스트는 하나의 노드에서 모든 노드로의 접근이 가능하다.

다른 연결 리스트들은 마지막 노드의 next를 NULL로 지정해준다. 하지만 원형 연결 리스트는 첫번째 노드에 접근하여 모든 노드의 링크를 따라 가야 할 필요가 없기 때문에 리스트의 끝에 노드를 추가하는 것이 다른 연결 리스트들 보다 용이하다.

만약 4라는 데이터를 삽입한다고 가정했을 때 다른 연결 리스트들은 모든 노드를 순회하여 마지막 노드를 찾고 해당 노드의 next를 null이 아닌 4를 가리키게 변경해줘야 한다.

반면에 원형 연결 리스트는 그림을 보는 것처럼 마지막 노드인 3은 첫 번째 노드인 1과 연결되어 있기 때문에 1이 아닌 4를 가리키게 바꿔주고 새로 삽입된 4라는 데이터의 next를 다시 첫 번째 노드인 1을 가리키게 변경해주면 된다.