List 란?

List (리스트)

• 원소간 순서 개념이 있다.

• 기본적인 연산 : 삽입, 삭제, 검색 등등

• 리스트를 구현하는 대표적인 두 가지 방법
  • 배열
  • 연결리스트

배열

• 장점

  • 랜덤 액세스가 가능하다 -> 검색 속도가 빠르다. ex) 4번째 칸 : 시작 주소 + 3 * (1칸의 크기)

• 단점

  • 크기가 고정 - reallocation이 필요하다.

  • 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다.

연결리스트

• 특징
  • 각각의 노드는 데이터 필드와 하나 이상의 링크 필드로 구성
  • 링크 필드는 다음 노드의 주소를 저장한다.
  • 첫 번쨰 노드의 주소는 따로 저장해야 한다.
  • 마지막 노드의 next 필드에는 NULL을 저장하여 연결리스트의 끝임을 표시한다.
• 장점
  • 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하다.
  • 길이의 제한이 없다.
• 단점
  • 랜덤 엑세스가 불가능하다 -> 검색속도 느리다.