배열과 링크드 리스트의 장단점은 각각 무엇입니까?

COBOL에서는 배열을 테이블이라 하고 첨자 또는 지표가 붙은 데이터명으로 테이블의 요소를 식별한다. 배열의 종류로는 1차원, 2차원, 3차원 배열이 사용되며 FORTRAN 77에서는 특이한 계산 형식의 7차원 배열까지 사용 가능하다.

- 인덱스로 접근 하므로 access 속도가 빠르다. 예를 들어, 100번째 데이터를 읽거나 쓰는 경우, 1번에 찾아갈 수 있다.

- 데이터 요소의 추가 및 삭제가 매우 느리다. 예를 들어, 100번째 데이터를 삭제하려면, 101번째 이후의 데이터를 앞으로 1칸씩 다 당겨야 한다.

- 서치에 좋다.

- 같은 자료형을 여러 개 쓸 때 유용,

- 크기가 정해져 있어서 공간낭비가 있거나 모자랄 때는 비효율적이다.

이것은 각 노드를 유용한 저장 공간에 그 위치에 상관없이 저장시키고, 각 노드의 관련성을 노드에 보관하여 1차원 배열 관계를 유지하도록 함으로써 중간 노드의 삽입, 제거를 손쉽게 할 수 있는 리스트로 각 노드는 링크(또는 포인터) 부분을 가지며, 그 노드와 관련 있는 다음 노드의 주소를 그 값으로 가진다. 다시 말하면 선형 리스트의 노드 배열이 어드레스와 일치하지 않고 기억 공간에 독립적으로 이루어진 리스트를 말한다.

- 링크(포인터)로 접근하므로, access 속도가 느리다. 예를 들어, 100번째 데이터를 읽거나 변경하려면 100회의 링크를 거쳐야 한다.

- 데이터 요소의 추가 및 삭제가 빠르다. 예를 들어, 100번째 데이터를 삭제하는 것은 100번째 노드를 찾은 후, 1번에 삭제할 수 있다. 즉, 99번째에서 101번째를 가리키게 링크만 바꾸면 된다. (물론, 구현에서는 100번째 노드를 free()도 해야 한다)

- 서치에 취약. 예를 들어, 정렬된 1000개의 데이터 중에서 513이라는 값이 있는지를 파악하려면, linear search를 해야만 한다. 반면에 배열은 binary search를 할 수 있다.

그래서 일반적으로 데이터의 크기가 고정되어 있으면 배열이 좋고, 데이터의 크기가 변하면서 삭제, 삽입을 많이 하면 링크드 리스트가 좋다.