[자료구조] 3.2 배열을 이용한 리스트의 구현 (7)

배열을 이용한 리스트의 구현 (7)

배열 기반 리스트

장단점

장점

• 데이터 참조가 쉽다 인덱스 값으로 어느 위치든 접근이 용이함

단점

• 배열의 길이가 초기에 결정된다
  • 선언할 때 길이를 결정하기 때문에 길이가 고정되어 변동이 불가하다
• 데이터 삭제시 데이터의 이동(복사)가 빈번하다
  • 배열 중간에 데이터가 삭제되는 경우 삭제 위치를 기준으로 기존의 데이터들이 한칸씩 당겨져서 빈 공간을 채운다.
  • 최악의 경우 데이터 수(N)만큼 이동이 발생 할 수 있다.
• 데이터 삽입의 데이터 이동(복사)거 빈번하다
  • 배열 중간에 삽입하고자 하는 경우 삽입 위치를 기준으로 기존의 데이터들을 한칸씩 밀어내서 공간을 확보한다.
  • 최악의 경우 데이터 수(N)만큼 이동이 발생 할 수 있다.

연결리스트와 비교

• 연결리스트 => 배열 기반 리스트의 단점을 보완 가능

  

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의
  
• 자료구조