연결 자료구조와 연결 리스트

연결 자료구조

연결 자료구조란?

• 연속적 물리 주소에 의해 원소 순서를 표현하는 순차 자료구조와 달리,
  각 원소에 저장되어 있는 다음 원소의 주소(링크)에 의해 순서가 연결되는 구현 방식

연결 자료구조의 특징

• 메모리 저장 방식
  • 메모리에 저장된 물리적 위치나 물리적 순서에 상관없이 링크에 의해 논리적인 순서를 표현하는 구현 방식
• 연산 특징
  • 삽입·삭 연산을 하여 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적 순서는 변경되지 않는다.
• 프로그램 기법
  • 포인터를 이용한 구현

연결 자료구조의 원소

• 연결 자료구조의 원소는 노드(Node)라고 부른다.
• 노드는 <원소, 주소> 단위로 구성된다.
  • 원소
    • 원소에는 실제로 저장할 데이터가 저장된다.
    • 데이터 필드라고 부른다.
    • 저장할 원소의 형태에 따라 한 개 이상으로 구성할 수 있다.
  • 주소
    • 주소에는 연결된 다믕 원소에 대한 주소가 저장된다.
    • 링크 필드라고 부른다.
      • 포인터 또는 링크 또는 참조라고 부르기도 한다.
    • 포인터 변수를 이용하여 주소값을 저장한다.

연결 리스트

연결 리스트의 기본 구조

• 연결 리스트는 기본적으로 3가지 노드로 구성되있다.

시작 노드

• 연결 리스트의 첫번째 노드
• 경우에 따라서 데이터 필드가 존재하지 않을 수도 있다.

중간 노드

• 시작 노드와 종료 노드 사이의 모든 노드
• 기본적인 노드 구조인 <원소, 주소>를 따른다.
• 링크 필드에는 항상 다음 노드의 주소가 저장되어 있다.

종료 노드

• 연결 리스트의 마지막 노드
• 더 이상 연결할 노드가 없기 때문에 링크 필드에는 NULL이 저장된다.

단순 연결 리스트 (Singly Linked List)

단순 연결 리스트란?

• 노드의 링크 필드가 하나인 연결 리스트
• 링크 필드는 다음 노드와 연결되는 구조다.
• 연결 리스트 또는 선형 연결 리스트 또는 단순 연결 선형 리스트라고도 부른다.

단순 연결 리스트의 삽입 연산

1. 삽입할 노드를 준비한다.
2. 새 노드의 데이터 필드에 값을 저장한다.
3. 새 노드의 링크값을 지정한다.
4. 리스트의 앞 노드에 새 노드를 연결한다.

단순 연결 리스트의 삭제 연산

1. 삭제할 노드의 앞 노드를 찾는다.
2. 앞 노드에 삭제할 노드의 링크 필드 값을 저장한다.
3. 삭제할 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트란?

• 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트 구조를 원형으로 만든 연결 리스트
• 삽입·삭제 연산은 단순 연결 리스트와 큰 차이점이 없다.
  • 중간에 연결이 끊어진 지점이 없게만 잘 연결하면 된다.
  • 만약 노드가 1개라면 해당 노드의 링크 필드는 자기 자신의 주소를 가리키게 된다.

이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트란?

• 단순/원형 연결 리스트는 리스트의 링크가 한 방향으로만 설계되어 반대 방향으로는 순회할 수 없다.
• 단방향 순회의 문제점을 고쳐서 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
• 단순/원형 리스트는 링크 필드가 1개지만 이중 연결 리스트는 링크 필드가 2개다.
  • 이중 연결 리스트의 링크 필드는 왼쪽/오른쪽 노드와 연결하는 역할을 하기 때문에
    실제 정의하는 방식에 따라 다르긴 하지만 각각 L-Link(왼쪽 노드 연결용)와 R-Link(오른쪽 노드 연결용)라고 부르기도 한다.
  • 시작 노드의 L-Link와 종료 노드의 R-Link는 각각 NULL로 저장된다.
  • 어차피 양방향 순회가 가능하기 때문에 원형 연결 리스트처럼 시작 노드와 종료 노드를 연결하지는 않는다.

이중 연결 리스트의 삽입 연산

1. 삽입할 노드를 준비한다.
2. 새 노드의 데이터 필드에 값을 저장한다.
3. 새 노드 왼쪽 노드의 오른쪽 링크 필드에 있던 값을 새 노드의 오른쪽 링크 필드에 저장한다.
4. 왼쪽 노드의 오른쪽 링크 필드에 새 노드의 주소를 저장한다.
5. 새 노드 오른쪽 노드의 왼쪽 링크 필드에 있던 값을 새 노드의 왼쪽 링크 필드에 저장한다.
6. 오른쪽 노드의 왼쪽 링크 필드에 새 노드의 주소를 저장한다.
7. 노드를 순서대로 연결한다.

이중 연결 리스트의 삭제 연산

1. 삭제할 노드의 왼쪽 노드와 오른쪽 노드를 찾는다.
2. 삭제할 노드의 오른쪽 노드의 주소를 삭제할 노드의 왼쪽 노드의 오른쪽 링크 필드에 저장한다.
3. 삭제할 노드의 왼쪽 노드의 주소를 삭제할 노드의 오른쪽 노드의 왼쪽 링크 필드에 저장한다.
4. 노드를 순서대로 연결한다.