선형 자료 구조

일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열이다. 배열과 같이 일렬로 늘어선 자료들을 저장하기 위해 동적 배열과 연결 리스트가 사용된다.

동적 배열

배열의 큰 문제 중 하나는 처음에 배열을 선언할 때 배열의 크기를 지정하여, 그이상의 자료를 집어 넣을 수 없다는 것이다.
동적 배열은 자료의 개수가 변함에 따라 크기가 변경된다.
또한 동적 배열은 배열의 특성을 그대로 이어 받았다.

• 원소들은 메모리의 연속된 위치에 저장된다.
• 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.
• 배열의 크기를 변경하는 resize() 연산이 가능하다.
  => 배열의 크기 N에 비례하는 시간이 걸린다.
• 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append()연산이 가능하다.

연결 리스트

• 배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는 것은 시간이 오래걸린다.
• 연결 리스트는 특정 위치에서의 삽입과 삭제를 상수 시간에 할수 있게 해준다.
• 연결 리스트는 원소들이 연속된 공간이 아닌 여기저기 흩어진 메모리에 존재한다.
• 특정한 원소를 search하는 건 리스트의 head부분 부터 하나씩 따라가서 찾는다.
  => 시간은 리스트의 길이에 비례한다.
• 새 node 삽입과 삭제는 간단하다.
  => 삽입은 원하는 위치와 연결된 리스트에 새로운 노드를 만들어 연결하면 되고, 삭제는 원하는 리스트를 찾아 연결을 해지해주면 된다.

동적 배열과 연결 리스트 비교.

둘의 가장 큰 차이점은 삽입과 삭제 그리고 임의의 원소에 접근할 때 걸리는 시간이다.
동적 배열은 특정 위치에 삽입과 삭제를 하기 위해서는 전에 존재하던 요소들의 이동까지 필요하기 때문에 많은 시간이 걸리지만, 연결 리스트는 새로운 노드를 추가해서 연결하거나, 해당 노드 연결을 해지하면, 문제가 해결된다.
임의의 원소에 접근할 때는 동적 배열에서는 인덱스로 쉽게 접근할 수 있지만,
연결 리스트는 head부터 시작하여, 탐색하면서 가야되기 때문에, 많은 시간이 걸린다.

REFERENCE

프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 - 구종만