연결 리스트 - 선형 리스트

연결 리스트

• 단일 연결 리스트
• 원형 연결 리스트
• 이중 연결 리스트

선형 리스트(linear list)

• 각 데이터가 배열과 같이 연속되는 기억장소에 순차적으로 저장되는 자료 구조
• 1차원 배열과 비슷한 구조이지만, 원소의 개수가 유동적
• 원소를 나열한 순서가 원소들의 순서가 됨
• 원소들의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조로 되어 있음
• 순차 자료구조에는 원소들이 순서대로 연속 저장되어 있기 때문에 시작위치와 원소의 길이를 알면 특정 원소의 위치를 알 수 있음

• 리스트에서 처리할 수 있는 연산

  • 길이 : 리스트의 길이를 구하는 연산
  • 접근 : 리스트의 내용을 조사하거나 변경하기 위해 위치를 찾는 연산
  • 검색 : 리스트의 노드들 중에서 필요한 노드 (i번째)를 찾는 연산
  • 저장 : i번째에 노드에 새로운 값을 기억시키는 연산
  • 삽입 : 리스트에 새로운 노드를 삽입시키는 연산
  • 삭제 : 리스테엇 노드를 제거하는 연산
  • 복사 : 리스트의 전체 또는 일부를 복사하여 새로운 노드(리스트)를 만드는 연산
  • 정렬 : 어떤 기준으로 리스트를 정렬(오름차순/내림차순)하는 연산
  • 병렬 : 둘 또는 그 이상의 리스트를 하나의 리스트로 합치는 연산
  • 분리 : 한 리스트를 둘 또는 그 이상의 리스트로 나누는 연산

• 선형 리스트의 특징

  • 기억 장소를 최대로 이용할 수 있는 구조이지만
  • 기억 장소에 저장되어 있는 정보들의 삽입, 삭제, 교환 등의 변화 시에는 복잡한 처리 필요
    • 삽입 및 삭제 후에는 리스트를 다시 정리하여 전체 리스트의 순서를 유지하는 작업 필요
    • 자료 이동이 많음
  • 따라서, 항목 이동에 관련된 수행 시간을 줄이기 위해 순서리스트를 비순차적으로 표현하는 것이 필요 (연결 리스트 : linked list)

• 선형 리스트에 노드 삽입

  • 3번에 새로운 노드를 삽입 시
  • 세 번 이동하여 3을 비워둔 상태에서 새로운 노드 삽입

• 선형 리스트의 단점
  • 데이터를 중간에 삽입하거나 중간 데이터를 삭제할 경우 많은 양의 데이터 이동 발생
  • 특히 데이터가 많을 경우 이동해야 하는 데이터 수가 더 많아짐
  • 또한, 크기가 다양한 여러 개의 선형 리스트들을 조작할 때 각각의 리스트에 대해 최대 크기를 가진 배열을 처음부터 준비해 두어야 하므로 기억 장소 낭비
  • 임의의 위치에 데이터를 삽입하거나 삭제가 용이하고 기억 장소를 낭비하지 않으며 삭제와 삽입 연산에 소요되는 시간을 절약하기 위한 새로운 형태의 선형 리스트(단일 연결 리스트 (singly linked list)) 필요