3. 기초 데이터구조 - 배열, 연결 리스트

기초 데이터구조

배열^Array

순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들을 배열이라 한다. 배열은 아래의 요소를 갖는다.

• 배열명: V
• 배열 크기: N
• 배열 인덱스: i
• 배열 원소: V[i]
• 배열 표시V[LB..UB]
  • 이때, lower bound는 0이 아닐 수도 있다.
  • UB는 원소의 갯수가 아니라, 마지막 원소의 인덱스이다.

컴파일 시, 배열의 셀들은 베이스라 불리는 배열의 첫째 셀 위치부터 차례대로 할당된다. 각 셀은 배열로부터 오프셋^offset만큼 떨어지게 할당된다. (오프셋은 0 ~ n)

다차원 배열

다차원으로 할당된 배열

메모리 할당은 저차원 축을 우선하여 할당한다.

LB가 0인 2차원 배열 V[UB₁, UB₂]에서 V[k₁, k₂]의 오프셋은 아래와 같다.

[(k₁ - LB₁)(UB₂ - LB₂ + 1)] + (k₂ - LB₂)

Lower bound를 모두 0으로 놓고 정리하면,

[(k₁)(UB₂ + 1)] + (k₂)

(UB₂+1)개의 원소를 갖는 행들을 k₁개 할당하고, 그 다음 행에서 k₂의 인덱스를 갖는 원소의 오프셋이 된다.

연결리스트^{Linked List}

동적 메모리 상에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들

• 연결리스트명 L: 연결리스트의 시작 위치, 첫 노드의 주소
• 연결리스트 크기 n: 연결리스트의 노드 수

연결리스트의 종류

• 단일^singly 연결리스트
• 이중^doubly 연결리스트
• 원형^circularly 연결리스트
• 헤더 및 트레일러 연결리스트^{linked lists with header and trailer}
• 이들의 복합

노드에 의한 메모리 할당

노드를 위한 메모리의 동적 할당과 해제는 실행 중에 system call에 의해 처리된다.

• getnode(): 노드를 할당하고 그 주소를 반환 (메모리가 고갈되는 등 실패하면 null을 반환)
• putnode(i): 주소 i의 노드에 할당되었던 메모리를 해제

단일 연결리스트

연속 노드로 구성된, 가장 단순한 연결 데이터구조.
노드는 하나의 다음 노드 주소를 갖고, 없다면 null을 저장한다. 접근점은 첫 노드인 헤드노드의 주소이다.

이중 연결리스트

추가 링크를 사용하여 역방향 순회가 가능하다. 노드는 다음 노드와 이전 노드의 주소를 갖고, 접근점은 헤드노드나 테일노드의 주소이다.

원형 연결리스트

마지막 노드의 링크가 헤드노드의 주소인 연결리스트로, 접근점은 헤드노드의 주소이다.

특별노드

헤드노드 바로 앞에 특별한 헤더 노드를 추가하여 작업 편의성을 증진 할 수 있다. 같은 목적으로 테일노드 바로 뒤에 트레일러 노드를 추가할 수도 있다.

헤더와 트레일러 노드는 더미 원소를 저장한다. 특별노드를 포함하는 연결리스트의 접근점은 헤더 혹은 트레일러 노드의 주소이다.

원형 이중 연결리스트

이중 연결리스트를 원형으로 구성하여, 첫 노드의 이전 노드는 마지막 노드, 마지막 노드의 다음 노드는 첫 노드가 되도록 구성한 연결리스트