연결리스트(linked list)

동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들
  • 연결리스트 명(linked list name), L : 연결리스트의 시작 위치, 즉 첫 노드의 주소
  • 연결리스트 크기(linked list size), n : 연결리스트 내 노드 수

 

동적메모리와 노드

  • 동적메모리(dynamic memory) : 프로그램 실행 시 사용 가능한 주메모리의 한 구역
  • 노드(node) : 한 개의 데이터원소를 저장하기 위해 동적메모리에 할당된 메모리

노드를 위한 메모리의 할당(allocation)과 해제(deallocation)는 실행시간에 시스템 콜에 의해 처리된다.

 

각 시스템콜을 표현하는 의사코드 명령

  • getnode() : 노드를 할당하고 그 노드의 주소를 반환. 만약 동적 메모리가 고갈된 시점이면 null 을 반환.
  • putnode(i) : 주소 i의 노드에 할당되었던 메모리의 사용을 해제하고, 이를 동적 메모리에 반환(메모리 재활용을 위함)

이와 같은 동적메모리 매커니즘을 활용하여, 연결리스트를 여러 가지 형태로 구현할 수 있다.

  • 단일 연결리스트
  • 이중 연결리스트
  • 원형 연결리스트
  • 헤더 및 트레일러 연결리스트
  • 이들의 복합

 

단일 연결리스트(singly linked list)

연속 노드로 구성된 가장 단순한 연결 데이터 구조

 

단일연결리스트의 노드

단일연결리스트의 각 노드가 저장하는 데이터

  • 원소(element) : 데이터 원소
  • 링크(link) : 다음(next) 노드의 주소. 만약 다음 노드가 없다면 널링크(Ø)를 저장

 

단일연결리스트의 접근점

  • 연결리스트 전체에 대한 참조로 사용하는 첫 노드의 주소, 헤드노드(head node)라고도 한다.
  • 그림 3-10 (상) 에서 단일연결리스트에 대한 접근점은 헤드노드의 주소 L이다.
  • 그림 3-10 (하) 에서 초기화되거나 비어있는 단일연결리스트의 헤드노드의 주소 L은 null(Ø)이다.

 

이중연결리스트(doubly linked list)

단일연결리스트의 각 노드에 링크를 하나 더 추가하여, 역방향 순회도 가능하도록 만든 연결리스트

 

이중연결리스트의 노드

 

이중연결리스트의 각 노드가 저장하는 데이터

  • 원소(element) : 데이터 원소
  • 링크(link) : 다음(next) 노드의 주소. 만약 다음 노드가 없다면 널링크(Ø)를 저장
  • 링크(link) : 이전(prev) 노드의 주소. 만약 이전 노드가 없다면 널링크(Ø)를 저장 

 

이중연결리스트의 접근점

  • 헤드노드(head node), Head : 연결리스트 전체에 대한 참조로 사용하는 첫 노드의 주소
  • 테일노드(tail node), Tail : 연결리스트 전체에 대한 참조로 사용하는 마지막 노드의 주소
  • 그림 3-12 (상) 에서 이중연결리스트에 대한 접근점은 헤드노드의 주소 Head 혹은 테일노드의 주소 Tail 이다.
  • 그림 3-12 (하) 에서 초기화되거나 비어있는 이중연결리스트의 Head 와 Tail 값은 모두 null(Ø)이다.

 

원형 연결리스트(circularly linked list)

단일연결리스트의 마지막 노드의 링크에 헤드노드의 주소를 저장하여 만든 연결리스트

 

원형연결리스트의 접근점

  • 헤드노드의 주소, L : 원형연결리스트 전체에 대한 참조로 사용하는 첫 노드의 주소
  • 그림 3-13 (상) 에서 원형연결리스트에 대한 접근점은 헤드노드의 주소 L 이다
  • 그림 3-13 (하) 에서 초기화되거나 비어있는 원형연결리스트의 L 은 null(Ø)이다.

 

헤더와 트레일러

작업의 편의를 위해 추가하는 특별 노드(special node) == 모조 노드 (dummy node)
  • 헤더 노드(header node), H : 헤드노드 바로 앞에 추가하여 사용할 수 있다.
  • 트레일러 노드(trailer node), T : 테일노드 바로 뒤에 추가하여 사용할 수 있다.

해당 노드에는 아무 원소도 저장하지 않아서 특별 노드(special node)라고 불리기도 하고,

실제 데이터 원소가 아닌 모조 원소를 저장하기 때문에 모조 노드(dummy node)라고 불리기도 한다.

 

헤드노드 vs 헤더노드

  • 헤드노드 : 실제 데이터원소를 저장하는 노드
  • 헤더노드 : 실제 데이터원소를 저장하지 않는 특별 노드

 

특별 노드를 사용하는 연결리스트에 대한 접근점

  • 헤더노드의 주소 또는 트레일러의 주소
  • 그림에서 헤더노드의 원소 필드가 흰 바탕으로 표시된 것은, 해당 필드의 값이 없거나 모조라는 의미이다.
  • 그림 3-14 (상) 에서 헤더를 사용한 단일연결리스트에 대한 접근점은 헤더노드의 주소 H 이다
  • 그림 3-14 (하) 에서 초기화되거나 비어 있는, 헤더를 사용한 단일연결리스트의 H 는 null(Ø)이다.

 

그 외의 연결리스트

앞서 제시한 기본형 연결리스트들과 특별 노드를 결합하여, 다양한 형태의 연결리스트들을 구축할 수 있다.
  • 다음 그림들의 (하) 부분은 초기화되거나 비어있는 연결리스트를 나타낸다.

저작자표시

티스토리툴바