LIST

• 크게 순차 LIST와 연결 LIST로 나뉜다.

순차 LIST

• 배열을 기반으로 구현된 list

  • 구현 방법:
    1차원 배열에 항목들을 순서대로 저장
    데이터 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 구현 가능

  • 데이터 접근
    배열의 인덱스를 이용해 원하는 위치의 데이터에 접근 할 수 있음.

  • 삽입 연산
    삽입 위치 다음의 항목들을 제일 뒤에 있는 원소부터 하나씩 이동해야 함

  • 삭제 연산
    삭제 위치 다음의 항목들을 삭제 위치 바로 앞에 부터 하나씩 이동해야 함

• 단점
  자료의 삽입 삭제 연산에서 연속적인 메모리 배열을 위해 원들을 이동 시키는 작업이 필요함
  즉, 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날 수록 작업에 소요되는 시간이 크게 증가한다.

  또한, 배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모이릐 낭비를 초래 할 수도 있고, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야하는 경우가 발생할 수도 있음.

연결 LIST

• 메모리의 동적 할당을 기반으로 구현된 list

  • 특징

    1. 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치 하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.
    2. 링크를 통해 원소에 접근하므로, 순차 list에서 물리적인 순서를 맞추기 위한 작업이 필요하지 않음
    3. 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능

  • 단점

    1. 구현이 배열 list보다 복잡하다.
    2. 위치를 알아도 접근하려면 맨 앞부터 혹은 맨뒤부터 순차적으로 탐색해서 찾아와야한다.
       즉, 순차 list보다 검색이 조금 더 느리다.