[자료구조] 04. List

본 내용은 필자가 학부 자료구조 수업내용을 공부하기 위해 정리한 것임을 알려드립니다.

4.1. 1차원 자료구조

우리는 다양한 앱을 사용한다 그런 다양한 앱을 통해 자료를 관리한다. 자세히 들여다보면 우리는 자료의 list를 관리한다.

자료의 관리는 ‘추가’, ‘검색’, ‘제거’로 이루어진다.

우리는 주소록 App에 새로 A라는 친구 번호를 ‘추가’하고, ‘제거’를 통해 B의 전화번호를 삭제한다. 하지만 사용빈도를 따져봤을 때 추가, 제거 보다는 ‘검색’ 연산을 통해 주소록에 저장 된 지인의 번호를 검색할 때가 가장 많다고 볼 수 있다.
따라서 검색이 잘 되는 자료구조가 가장 좋은 자료구조 라고 말할 수 있다.

List의 정의

1. 유한한 원소들의 나열 (a finite sequence of elements)
2. 각 원소들은 index에 대응 된다.
3. (index, element) 쌍

List 구현 방법

• 배열 (Array) : index에 기반한 구현

• 연결 리스트 (Linked List) : Pointer 에 기반한 구현

  배열

• 연속된 기억공간

  • 메모리에 배열의 크기보다 더 큰 공간이 허용되어야 한다.

  연결리스트

• 원소 + 다음 원소의 주소

  • 메모리에 배열의 크기보다 더 큰 연속된 공간이 없을 때 사용한다.
  • Data + Link (다음 원소의 주소를 저장하는 Pointer)

List 저장 방법

검색

• 정렬된 list (Sorted List) (오름차순, 내림차순)
  • 예측 가능한 원소의 위치 : 성능이 좋음
• 정렬되지 않은 list (Unsorted list)
  • 원소의 위치를 예측할 수 없음 : 성능이 좋지 않음

추가

• 정렬된 list (Sorted List)

  • 들어갈 원소의 자리가 정해져 있으므로, 삽입할 원소가 원소들 사이라면 기존 원소들을 뒤로 한 칸씩 밀어야 한다.
  • 성능이 좋지 않음

• 정렬되지 않은 list (Unsorted list)

  • 아무 자리에나 원소 삽입 : 성능이 좋음

삭제

• 정렬되었거나, 정렬되지 않은 list 모두 원소 사이의 원소를 제거하면 자리를 앞으로 땡기는 작업 수행 : 성능이 좋지 않음