배열과 연결리스트는 데이터를 나열한다는 점에서 비슷하다. 하지만 배열과 연결 리스트는 엄연히 다르기 때문에 사용하기에 따라 프로그램의 성능이 달라지게 된다.
배열(Array)
- 배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. 그리고 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 데이터 접근 속도가 매우 빠르다. 그러나 배열은 데이터의 삽입/삭제에는 취약하다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다.
위의 그림을 보면 K라는 데이터가 3번째 위치에 삽입됨에 따라 C, D, E, F의 위치가 바꼈다. 삭제의 경우에도 위와 마찬가지로 반대로 처리된다. 지금은 데이터의 수가 적기 때문에 큰 문제는 없지만, 만약에 배열 데이터의 수가 10000개라고 하고 삽입/삭제가 빈번하게 일어난다고 가정을 하고 생각을 하면 프로그램은 데이터 삽입/삭제 때마다 데이터의 위치를 바꾸는데만 많은 리소스를 사용할 것이다. 이것은 매우 비효율적이다.
연결리스트(LinkedList)
- 연결리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않다. 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다. 때문에 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하고, 배열에 비해 속도가 떨어진다. 하지만 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 데이터 삽입/삭제는 용이하다.
위의 그림과 같이 삽입/삭제가 이루어지는 데이터의 링크만 변경하면 되므로 배열같이 다른 데이터에 영향을 많이 주지 않는다.
결론
- 데이터 양이 많지만 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어질 경우는 배열이 유리하고, 데이터 양이 그렇게 많지 않고, 데이터의 삽입/삭제가 빈번하게 이루어질 경우에는 연결리스트가 유리하다.
여러 자료구조 책을 보면 여러 자료구조를 소스로 표현되어 있는데 굳이 소스까지 외울 필요는 없다고 생각이 든다. 특별한 경우를 제외하고, C# 또는 JAVA 등과 같은 언어로 프로그래밍을 할 경우 이미 여러 자료구조를 사용하기 편하게 클래스화 시켜놓고 있기 때문에 하나하나 구현할 필요 없이 그냥 적절하게 쓰면 된다. 하지만 중요한 것은 구조와 특징은 정확하게 알고 있어야 한다는 점이다. 구조와 특징을 파악하고 있는 사람은 어떤 상황에서도 프로그래밍을 할 수 있다.
배열(Array)
- 배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. 그리고 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 데이터 접근 속도가 매우 빠르다. 그러나 배열은 데이터의 삽입/삭제에는 취약하다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다.
위의 그림을 보면 K라는 데이터가 3번째 위치에 삽입됨에 따라 C, D, E, F의 위치가 바꼈다. 삭제의 경우에도 위와 마찬가지로 반대로 처리된다. 지금은 데이터의 수가 적기 때문에 큰 문제는 없지만, 만약에 배열 데이터의 수가 10000개라고 하고 삽입/삭제가 빈번하게 일어난다고 가정을 하고 생각을 하면 프로그램은 데이터 삽입/삭제 때마다 데이터의 위치를 바꾸는데만 많은 리소스를 사용할 것이다. 이것은 매우 비효율적이다.
연결리스트(LinkedList)
- 연결리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않다. 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다. 때문에 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하고, 배열에 비해 속도가 떨어진다. 하지만 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 데이터 삽입/삭제는 용이하다.
위의 그림과 같이 삽입/삭제가 이루어지는 데이터의 링크만 변경하면 되므로 배열같이 다른 데이터에 영향을 많이 주지 않는다.
결론
- 데이터 양이 많지만 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어질 경우는 배열이 유리하고, 데이터 양이 그렇게 많지 않고, 데이터의 삽입/삭제가 빈번하게 이루어질 경우에는 연결리스트가 유리하다.
여러 자료구조 책을 보면 여러 자료구조를 소스로 표현되어 있는데 굳이 소스까지 외울 필요는 없다고 생각이 든다. 특별한 경우를 제외하고, C# 또는 JAVA 등과 같은 언어로 프로그래밍을 할 경우 이미 여러 자료구조를 사용하기 편하게 클래스화 시켜놓고 있기 때문에 하나하나 구현할 필요 없이 그냥 적절하게 쓰면 된다. 하지만 중요한 것은 구조와 특징은 정확하게 알고 있어야 한다는 점이다. 구조와 특징을 파악하고 있는 사람은 어떤 상황에서도 프로그래밍을 할 수 있다.