[자료구조] Java 배열(array)과 리스트(list) 비교

Java 배열(array)과 리스트(list) 비교

리스트(list)란 데이터를 순차적으로 나열해 놓은 집합을 가리키는 자료구조의 추상적인 개념으로 비슷한 성질의 데이터를 순서를 고려하여 그룹화 시키고자 할 때 주로 사용하는 자료구조이다.

1. 배열을 이용한 구현

배열을 이용하여 리스트(list)를 구현할때의 가장 큰 장점은 쉽게 구현할 수 있다는 점이다. 배열은 내부 인덱스를 가지고 데이터에 접근할 수 있으므로 인덱스의 번호가 곧 데이터들의 순서를 의미하기 때문에 데이터 삽입시 순차적으로 인덱스 값을 증가시키면서 저장하면 되고 데이터를 검색 할 때에도 인덱스를 가지고 직접 접근하여 빠르게 찾을 수 있다.

그리고 배열은 항상 인덱스 0부터 시작하기 때문에 첫 데이터를 쉽게 찾을 수 있으며 저장된 데이터의 수만 따로 관리하면 마지막 데이터도 쉽게 찾을 수 있기때문에 스택이나 큐의 구현도 쉽게 할 수 있다.

하지만 배열을 이용한 리스트(list)의 구현은 몇가지 단점을 가지고 있다.

배열은 생성할때 지정한 크기를 바꿀 수 없기 때문에 초기에 너무 큰 크기로 생성했을 경우 불필요한 메모리의 낭비가 발생하고 또한 저장할 데이터보다 작은 크기로 생성했을 경우에는 데이터를 다 저장할 수 없다.

이를 해결하기 위해 배열의 사이즈보다 많은 데이터를 담으려고 할 경우 크기가 더 큰 배열을 새로 생성하여 처리하도록 할 수 있지만 배열을 새로 생성하여 이전의 데이터를 모두 복사하는 작업을 수행해야 하므로 상당한 연산량이 필요하게 된다.

또한 데이터를 삽입하거나  삭제했을 경우 뒤의 데이터들을 모두 한칸씩 밀어주거나 앞으로 당겨주는 작업을 해야 하기 때문에 삽입/삭제 작업이 발생할 경우 평균적으로 데이터의수/2 만큼의 이동이 추가적으로 발생하게 된다.

이처럼 쉽게 구현할 수 있고 빠른 검색기능을 가지고 있지만 저장될 데이터의 수를 가늠하기 어렵거나 삽입과 삭제에 걸리는 시간 때문에 일반적으로 배열보다는 연결 리스트를 많이 사용한다.

[자료구조] JAVA 배열을 이용한 자료의 관리

2. 연결 리스트를 이용한 구현

연결 리스트(linked list)는 리스트 구현의 한 방법으로 일정한 순서를 가지는 자료들의 저장과 탐색을 효과적으로 관리하기 위하여 각 데이터 요소들에 이전데이터나 다음데이터를 가리키는 참조를 추가적으로 부여하여 자료들을 연결하는 방법을 말한다.

배열처럼 각 자료에 대하여 직접 인덱스를 부여하지 않고 이전 데이터나 다음 데이터에 대한 참조만 가지고 있으므로 데이터를 추가하거나 삭제시 연관된 모든 데이터의 인덱스를 변경할 필요 없이 이전데이터와 다음데이터에 대한 참조만 변경하면 되므로 효율적으로 동작할 수 있다.

각 자료는 이전 데이터나 다음 데이터에 대한 참조를 가져야 하므로 연결 리스트에 저장되는 데이터는 원본 데이터와 다른 데이터에 대한 참조를 표현한 구조여야 하며 이를 노드(node)라고 부른다. 즉 연결 리스트는 노드와 노드의 연결로 이루어진 자료구조인 셈이다.

연결 리스트도 몇가지 종류가 있는데 각 자료 요소들이 다음 데이터에 대한 참조를 가지고 있는 경우를 단순 연결 리스트(simple linked list)라고 하고 단순 연결 리스트의 마지막 자료에 대한 참조를 추가한 구조를 이중 말단 연결 리스트(double ended linked list)라고 하며 이전 데이터와 다음 데이터에 대한 참조를 모두 추가한 구조를 이중 연결 리스트(doubly linked list)라고 한다.

다음은 단순 연결 리스트에서 사용하는 노드의 기본적인 구조이다.

class Node {

   private Object data;
   private Node nextNode;

   Node(Object data){
     
         this.data = data;
         this.nextNode = null;
        
   }
}

각 노드는 실제 저장하는 데이터인 data 변수와 다음 노드를 가리키는 nextNode 변수로 이루어져 있다.

연결 리스트는 첫번째 노드를 가리키는 시작점이 필요한데 이러한 역할의 노드를 감시 노드(sentinel node)라고 하며 일반적으로 헤더라고 부른다. 헤더에는 리스트의 첫번째 노드를 가리키는 참조자만 존재하며 실제 데이터는 없다.

헤더가 가리키는 노드(nextNode)가 첫번째 노드이며 첫번째 노드의 nextNode가 두번째 노드, 두번째 노드의 nextNode가 세번째 노드가 된다.

이런식으로 첫번째 노드부터 마지막 노드까지 순차적으로 자신의 다음 노드를 가리키는 참조가 있기 때문에 데이터의 삽입과 삭제시 인접한 노드의 참조값만 바꿔주면 되기 때문에 빠른 속도로 처리가 가능한 것이다.

3. 배열과 연결 리스트의 장단점

리스트(list) 자료구조를 구현하는 방법으로 배열을 이용한 방법과 연결 리스트를 이용한 방법이 있다.

(1) 배열의 장단점

장점

- 구현이 쉽다

- 검색 성능이 좋다. 인덱스를 이용한 무작위 접근(random access)이 가능하므로 검색에서 빠른 성능을 기대할 수 있다.

- 순차 접근(sequential access)의 경우에도 배열은 데이터를 하나의 연속된 메모리 공간에 할당하므로 연결 리스트보다 빠른 성능을 보인다.

- 참조를 위한 추가적인 메모리 할당이 필요 없다.

단점

- 자료의 삽입과 삭제에 비효율적이다. 자료의 삽입과 삭제시 다음 항목의 모든 요소를 이동해야 하므로 많은 연산이 수행되어 비효율적이며 자료의 수와 비례하여 성능이 떨어진다.

- 크기를 바꿀 수 없다. 배열은 생성할 때 지정한 크기를 바꿀 수 없기 때문에 너무 크게 잡으면 메모리가 낭비되고 너무 작게 잡으면 그 이상의 자료를 저장할 수 없다. 새로운 배열을 만들어 사용하더라도 연산량이 많아져 효율이 떨어진다.

- 메모리의 재사용이 불가능하다. 배열은 초기 사이즈만큼의 메모리를 할당 받아 사용하기 때문에 데이터의 존재 유무와 상관없이 일정한 크기의 메모리를 점유한다. 즉 이미 삭제한 데이터라고 하더라도 배열 자체가 메모리에서 제거되지 않는 이상 삭제된 데이터의 메모리를 재사용 할 수 없다.

(2) 연결 리스트의 장단점

장점

- 자료의 삽입과 삭제에 효율적이다. 삽입이나 삭제할 자료의 전후 노드의 참조 관계만 수정해 주면 되기 때문에 삽입과 삭제하는 자료의 위치나 전체 자료수와 상관없이 일정한 성능으로 동작한다.

- 크기가 고정되어 있지 않다. 자료가 하나 삽입 될 때마다 생성되는 노드는 독립적인 공간의 메모리이기 때문에 물리적인 메모리의 범위 내에서는 그 수의 제한이 없다.

- 메모리의 재사용이 가능하다. 자료의 삭제시 해당 노드의 참조가 사라지므로 나중에 Garbage Collector에 의해 가용할 수 있는 메모리로 전환된다.

단점

- 배열에 비해 구현이 복잡하다.

- 검색 성능이 좋지 않다. 특정 순서의 자료를 검색하더라도 처음부터 순차적으로 검색을 해야 하므로 배열에 비해 검색시간이 많이 소요된다. 또한 각 요소를 구성하는 노드들이 독립된 객체이므로 메모리에 산재해 있게 되어 배열보다 긴 접근 시간이 필요하다.

- 참조를 위한 추가 메모리 할당이 필요하다. 배열은 요소 하나에 대해 실제 저장될 데이터만큼의 메모리가 필요하디만 연결 리스트는 추가적으로 인접한 데이터에 대한 참조를 필요로 하므로 데이터의 크기가 작을 경우 참조를 위한 추가적인 메모리가 오히려 더 크게 잡힐 수도 있다.

* 저장할 데이터의 최대 개수가 정해져 있고 리스트의 중간에 데이터를 삽입, 삭제하는 작업이 많지 않으며 인덱스를 이용한 빠른 검색이 필요할 경우에는 배열을 사용하는게 효율적

* 저장될 데이터의 개수가 정해져 있지 않고 리스트의 중간에 데이터를 삽입하거나 삭제하는 작업이 많고 삽입, 삭제에 비해 특정 위치의 데이터를 검색하는 작업이 많지 않을 경우 연결 리스트를 사용하는게 효율적

출처: https://hyeonstorage.tistory.com/258?category=578561 [개발이 하고 싶어요]