본문 바로가기
CS/자료구조

자료구조 슈도 코드 및 개념 요약 정리 : 배열, 스택, 큐, 연결 리스트, 이중 연결 리스트, 원형 연결 리스트

by Renechoi 2023. 12. 2.

배열

배열의 추상 자료형

1) Array create(n)::= 배열의 크기가 n인 빈 배열을 생성하고 배열을 반환한다; // n 크기의 배열을 생성
2) Element retrieve(a,i)::= if (Index)
   then {배열의 i번째에 해당하는 원소값 'e'를 반환한다;} 
   else {에러 메시지를 반환한다;} // 인덱스가 유효하면 i번째 원소 반환, 아니면 에러
3) Array store(a, i, e)::= if (i <- Index)
   then {배열 a의 i번째 위치에 원소값 'e'를 저장하고 배열 a를 반환한다;} 
   else {인덱스 i가 배열 a의 크기를 벗어나면 에러 메시지를 반환한다;} // 유효한 인덱스면 원소 저장, 아니면 에러

이 코드는 배열의 생성, 요소 검색, 요소 저장을 위한 추상 자료형(ADT)을 정의한다. 배열을 생성하고, 특정 인덱스에서 요소를 검색하거나 저장하는 기능을 포함한다.

  • Array create(n): 지정된 크기 n의 빈 배열을 생성하고 반환한다. 이 함수는 배열을 초기화하는 데 사용된다.
  • Element retrieve(a,i): 배열 a에서 주어진 인덱스 i에 있는 요소를 검색한다. 인덱스가 유효한 범위 내에 있으면 해당 요소를 반환하고, 그렇지 않으면 에러 메시지를 반환한다.
  • Array store(a, i, e): 배열 a의 인덱스 i 위치에 요소 e를 저장합니다. 인덱스가 배열의 크기 내에 있으면 요소를 저장하고 배열을 반환하며, 그렇지 않으면 에러 메시지를 반환한다.

배열의 생성

void create(int n) { // 정수 n을 매개변수로 받는 create 함수 정의
    int a[n]; // 크기가 n인 정수 배열 a 선언
    int i; // 반복문에 사용할 변수 i 선언
    for(i = 0; i < n; i++) { // 0부터 n-1까지 반복
        a[i] = 0; // 배열 a의 i번째 요소를 0으로 초기화
    }
}

이 코드는 주어진 크기 n에 대해 크기가 n인 정수 배열을 생성하고, 모든 요소를 0으로 초기화하는 함수 create를 정의한다. 배열은 지역 변수로 선언되어 함수가 종료되면 메모리에서 사라진다.

  • void create(int n): 이 함수는 크기가 n인 정수 배열을 생성하고, 배열의 모든 요소를 0으로 초기화한다. 배열은 스택 메모리에 할당되며, 함수가 종료되면 사라진다. 이 함수는 배열을 초기화하고 기본값을 설정하는 데 사용된다.

배열의 검색

#define array_size 5 // 배열의 크기를 5로 정의하는 매크로

int retrieve(int *a, int i) { // 정수 배열 포인터 a와 인덱스 i를 매개변수로 받는 retrieve 함수 정의
    if (i >= 0 && i < array_size) { // i가 0 이상이고 array_size 미만인 경우
        return a[i]; // 배열 a의 i번째 요소 반환
    } else { // 그렇지 않은 경우
        printf("Error\n"); // 에러 메시지 출력
        return -1; // -1 반환
    }
}

이 코드는 주어진 정수 배열 a에서 인덱스 i에 해당하는 요소를 검색하는 함수 retrieve를 정의한다. 함수는 인덱스가 유효한 범위 내에 있으면 해당 요소를 반환하고, 그렇지 않으면 에러 메시지를 출력하고 -1을 반환한다. 이 함수는 배열 내 특정 위치의 데이터를 안전하게 접근하고 검색하는 데 사용된다.

  • int retrieve(int *a, int i): 이 함수는 배열 a에서 인덱스 i에 해당하는 요소를 검색한다. 인덱스가 배열 크기 내에 있으면 해당 요소를 반환하고, 그렇지 않으면 에러 메시지를 출력하고 -1을 반환한다. 이 함수는 배열 내의 특정 요소에 안전하게 접근하는 데 사용된다.

배열의 저장

#define array_size 5 // array_size를 5로 정의
void store(int *a, int i, int e) { // 정수 포인터 a, 정수 i, 정수 e를 매개변수로 받는 store 함수 정의
    if(i >= 0 && i < array_size) { // i가 0 이상이고 array_size 미만인 경우
        a[i] = e; // 배열 a의 i번째 요소에 e를 저장
    } else {
        printf("Error\n"); // 그 외의 경우 에러 메시지 출력
    }
}

이 코드는 store라는 함수를 정의하여, 주어진 배열 a의 특정 인덱스 i 위치에 값을 e로 저장하는 기능을 수행한다. 배열의 크기는 array_size로 정의되어 있으며, 이 값이 5이므로 배열의 유효한 인덱스는 0부터 4까지이다. 인덱스가 유효 범위 내에 있을 때만 값을 저장하고, 그렇지 않으면 에러 메시지를 출력한다.

  • void store(int *a, int i, int e): 이 함수는 주어진 배열 a에 인덱스 i의 위치에 값 e를 저장한다. 인덱스가 유효한 범위 내에 있어야만 값을 저장할 수 있으며, 그렇지 않을 경우 에러 메시지를 출력한다. 이 함수는 배열의 특정 위치에 값을 저장하거나 수정하는 데 사용된다.

스택

스택의 추상 자료형

create

// 연산: stack e Stack, item G element, maxStackSize G positive integer인 모든 stack, item, maxStackSize에 대하여 다음과 같은 연산이 정의된다
// (stack은 0개 이상의 원소를 갖는 스택, item은 스택에 삽입되는 원소, maxStackSize는 스택의 최대 크기를 정의하는 정수).
- Stack CreateStack(maxStackSize)::=
  스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다; // maxStackSize 크기의 빈 스택을 생성하고 반환

이 코드는 CreateStack이라는 연산을 정의하며, 이 연산은 주어진 최대 크기(maxStackSize)를 가진 빈 스택을 생성하고 반환하는 기능을 한다. 여기서 stack은 0개 이상의 원소를 갖는 스택을 의미하고, item은 스택에 삽입되는 원소, maxStackSize는 스택의 최대 크기를 정의하는 정수이다.

  • Stack CreateStack(maxStackSize): 이 연산은 최대 크기가 maxStackSize인 스택을 생성하고 반환한다. 이 기능은 새로운 스택을 초기화하고 사용할 준비를 하는 데 사용된다.

push

// Stack Push(stack, item)::=
if (StackIsFull(stack)) {
    then {'stackFull'을 출력한다;} // 스택이 가득 찼을 경우 'stackFull'을 출력
} else {
    스택의 가장 위에 item을 삽입하고, 스택을 반환한다; // 스택이 가득 차지 않았을 경우 item을 스택의 맨 위에 삽입하고 스택을 반환
}

이 코드는 Push라는 연산을 정의하며, 이 연산은 주어진 스택(stack)에 새로운 원소(item)를 삽입하는 기능을 한다. 만약 스택이 가득 찼다면 'stackFull' 메시지를 출력하고, 그렇지 않다면 새로운 원소를 스택의 가장 위에 삽입한 후 스택을 반환한다.

  • Stack Push(stack, item): 이 연산은 주어진 스택에 새로운 원소를 삽입한다. 스택이 가득 찼을 경우 'stackFull' 메시지를 출력하고, 그렇지 않으면 새로운 원소를 스택의 가장 위에 삽입한 후 스택을 반환한다. 이 기능은 스택에 데이터를 추가하는 데 사용된다.

pop

Element Pop(stack) ::= // 스택에서 pop 연산을 수행하는 함수 정의
    if (StacklsEmpty(stack)) // 스택이 비어있는지 확인
        then {'stackEmpty'을 출력한다;} // 스택이 비어있다면 'stackEmpty' 출력
    else { 스택의 가장 위에 있는 원소(element)를 // 스택이 비어있지 않다면
        삭제하고 반환한다; } // 가장 위에 있는 원소를 삭제하고 반환

이 코드는 스택에서 pop 연산을 수행하는 함수를 정의한다. 스택이 비어있으면 "stackEmpty"를 출력하고, 비어있지 않으면 스택의 가장 위에 있는 원소를 삭제하고 반환한다.

  • Element Pop(stack): 스택의 상단에서 원소를 제거하고 그 원소를 반환한다. 스택이 비어 있을 경우, "stackEmpty" 메시지를 출력한다. 이 함수는 스택의 마지막 원소를 제거하고 그 값을 반환하는 데 사용된다.

isFull & isEmpty

Boolean StacklsFull(stack, maxStackSize) ::= // 스택이 가득 찼는지 확인하는 함수 정의
    if ((stack 의 elements 의 개수) == maxStackSize) // 스택의 원소 개수가 최대 크기와 같으면
        then {'TRUE' 값을 반환한다;} // 'TRUE' 반환
    else {'FALSE' 값을 반환한다;} // 아니면 'FALSE' 반환

Boolean StacklsEmpty(stack) ::= // 스택이 비어있는지 확인하는 함수 정의
    if(stack == CreateStack(maxStackSize)) // 스택이 비어있는 초기 상태와 같으면
        then {'TRUE' 값을 반환한다;} // 'TRUE' 반환
    else {'FALSE' 값을 반환한다;} // 아니면 'FALSE' 반환

이 코드는 스택이 가득 찼는지(StacklsFull)와 비어 있는지(StacklsEmpty)를 확인하는 함수들을 정의한다. StacklsFull은 스택의 원소 개수가 최대 크기와 같으면 TRUE를, 그렇지 않으면 FALSE를 반환한다. StacklsEmpty는 스택이 비어 있는 초기 상태와 같으면 TRUE를, 그렇지 않으면 FALSE를 반환한다.

  • Boolean StacklsFull(stack, maxStackSize): 이 함수는 스택이 최대 크기에 도달했는지 확인한다. 스택의 원소 수가 최대 크기와 같으면 TRUE, 아니면 FALSE를 반환한다.
  • Boolean StacklsEmpty(stack): 이 함수는 스택이 비어 있는지 확인한다. 스택이 비어 있는 초기 상태와 같으면 TRUE, 그렇지 않으면 FALSE를 반환한다.

스택의 생성

#define STACK_SIZE 10 // 스택의 최대 크기를 10으로 정의
typedef int element;  // 스택에 저장될 요소의 타입을 int로 정의
element stack[STACK_SIZE]; // 크기가 STACK_SIZE인 배열로 스택 구현
int top = -1; // 스택의 맨 위 요소를 가리키는 top 변수를 -1로 초기화

이 코드는 크기가 10인 정수 배열을 사용하여 스택을 구현한다. 스택의 각 요소는 int 타입이며, top 변수는 스택의 맨 위 요소의 인덱스를 나타낸다. 초기에 top은 -1로 설정되어 스택이 비어있음을 나타낸다.

  • #define STACK_SIZE 10: 스택의 최대 크기를 10으로 정의한다.
  • typedef int element: 스택에서 사용할 요소의 타입을 int로 정의한다.
  • element stack[STACK_SIZE]: 크기가 10인 배열을 선언하여 스택을 구현한다.
  • int top = -1: 스택이 비어있음을 나타내기 위해 top을 -1로 초기화한다.

스택의 삭제

1) int pop() {
2)     if (top == -1) {
3)         return StackIsEmpty(); // 스택이 비어있으면 StackIsEmpty 함수 호출
4)     }
5)     else return stack[top--]; // 스택이 비어있지 않으면 top의 요소를 반환하고 top 감소

이 코드는 스택에서 가장 위에 있는 요소를 제거하고 반환하는 pop 함수를 정의한다. 스택이 비어있으면 StackIsEmpty 함수가 호출되고, 그렇지 않으면 현재 top에 위치한 요소를 반환한 후 top의 값을 감소시킨다.

  • int pop(): 스택에서 요소를 제거하는 함수를 정의한다.
  • if (top == -1): 스택이 비어있는지 확인한다. 비어있으면 StackIsEmpty 함수를 호출한다.
  • return stack[top--]: 스택이 비어있지 않으면 현재 top에 위치한 요소를 반환하고 top을 감소시킨다.

스택의 삽입

void push(int item) { // 정수 item을 매개변수로 받는 push 함수 정의
    if (top >= STACK_SIZE-1) // 스택이 가득 차있는지 확인
        return StackIsFull(); // 스택이 가득 찼으면 StackIsFull 함수 호출
    else
        stack[++top] = item; // 스택이 가득 차지 않았으면 top을 증가시키고 해당 위치에 item 저장
}

이 코드는 스택 자료구조에 새로운 요소를 추가하는 push 함수를 정의한다. 스택이 가득 차 있지 않을 경우, top 인덱스를 하나 증가시키고 그 위치에 새로운 요소(item)를 저장한다. 만약 스택이 가득 차 있으면, StackIsFull 함수를 호출하여 처리한다.

후위 표기식 알고리즘

element evalPostfix(char *exp) { // 문자열 exp를 매개변수로 받는 evalPostfix 함수 정의
    int oper1, oper2, value, i = 0; // 연산에 필요한 변수 선언
    int length = strlen(exp); // exp의 길이 계산
    char symbol; // 현재 문자를 저장할 변수
    top = -1; // top 초기화

    for (i = 0; i < length; i++) { // exp를 순회
        symbol = exp[i]; // 현재 문자 저장
        if (symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/') { // 연산자가 아닌 경우
            value = symbol - '0'; // 문자를 정수로 변환
            push(value); // 변환된 값을 스택에 push
        } else { // 연산자인 경우
            oper2 = pop(); // 스택에서 두 번째 피연산자 pop
            oper1 = pop(); // 스택에서 첫 번째 피연산자 pop
            switch(symbol) { // 연산자에 따라 연산 수행
                case '+': push(oper1 + oper2); break; // 더하기 연산 후 결과를 스택에 push
                case '-': push(oper1 - oper2); break; // 빼기 연산 후 결과를 스택에 push
                case '*': push(oper1 * oper2); break; // 곱하기 연산 후 결과를 스택에 push
                case '/': push(oper1 / oper2); break; // 나누기 연산 후 결과를 스택에 push
            }
        }
    }
    return pop(); // 최종 결과를 스택에서 pop하여 반환
}

이 코드는 후위 표기식을 계산하는 evalPostfix 함수를 정의한다. 이 함수는 후위 표기식을 나타내는 문자열 exp를 순회하면서 각 문자가 연산자인지, 피연산자인지를 확인한다. 피연산자는 스택에 저장하고, 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내 연산을 수행한 후 그 결과를 다시 스택에 저장한다. 모든 문자를 처리한 후, 스택에 남아 있는 값이 최종 계산 결과이다.

큐

큐의 추상 자료형

큐의 연산

queue Queue, item Element, maxQueueSize positive integer인 모든 Queue, Element, maxQueueSize에 대하여 다음과 같은 연산이 정의된다. 
(Queue는 0 개 이상의 원소를 갖는 행렬, Element는 큐에 삽입되는 원소, maxQueueSize는 큐의 최대 크기를 정의하는 정수).

이 부분은 큐 자료구조의 기본적인 개념과 그에 따른 연산이 정의되어 있다. 큐(Queue)는 0개 이상의 원소를 갖는 순차적 자료구조이며, 여기서 사용되는 요소(Element)는 큐에 삽입될 데이터를 의미한다. maxQueueSize는 큐의 최대 크기를 정의하는 양의 정수이다.

  • queue Queue, item Element, maxQueueSize positive integer: 큐(Queue)는 원소(Element)들을 순차적으로 저장하는 자료구조이다. 이는 큐의 최대 크기(maxQueueSize)가 정의된 상태에서 동작한다. 큐는 FIFO(First-In, First-Out) 방식으로 작동한다.

큐의 삽입

void Add_q(Queue queue, Element item) :=
if (IsFull_q(queue))
then {‘Queue is full’를 출력한다;}
else { 큐의 rear에서 item을 삽입하고,
큐를 반환한다;}

이 코드는 큐에 새로운 요소를 추가하는 함수 Add_q를 정의하고 있다. 먼저 큐가 가득 찼는지 확인하고, 만약 가득 찼다면 "Queue is full"이라는 메시지를 출력한다. 큐에 여유 공간이 있으면, 큐의 끝(rear)에 새로운 요소(item)을 삽입한다.

  • void Add_q(Queue queue, Element item): 이 함수는 큐(queue)에 새로운 요소(item)를 추가한다. 큐가 가득 찼는지 먼저 확인하고, 여유 공간이 있을 경우에만 새 요소를 큐의 끝에 추가한다. 이 함수는 큐에 새 데이터를 삽입하는 기능을 수행한다.

큐의 삭제

Element Delete_q(Queue queue) { // 큐에서 원소를 삭제하는 Delete_q 함수 정의
    if (IsEmpty_q(queue)) { // 큐가 비어있는지 확인
        printf("Queue is empty\n"); // 큐가 비어있다면 'Queue is empty'를 출력
    } else {
        Element item = queue.array[queue.front]; // front 위치의 원소를 item에 저장
        queue.front = (queue.front + 1) % queue.capacity; // front 위치를 업데이트
        return item; // 삭제된 원소 반환
    }
}

이 코드는 큐에서 원소를 삭제하는 기능을 수행한다. 큐가 비어 있는지 확인한 후, 비어 있지 않다면 큐의 front에 위치한 원소를 삭제하고 반환한다.

  • Element Delete_q(Queue queue): 이 함수는 큐에서 front에 위치한 원소를 삭제하고 반환한다. 큐가 비어있으면 메시지를 출력하고, 그렇지 않으면 front 위치의 원소를 삭제하고 반환한다.

큐의 isEmpty

Boolean IsEmpty_q(Queue queue) { // 큐가 비어있는지 확인하는 IsEmpty_q 함수 정의
    return (queue.rear == queue.front); // rear와 front가 같으면 TRUE, 그렇지 않으면 FALSE 반환
}

이 코드는 큐가 비어 있는지 여부를 확인하는 기능을 수행한다. 큐의 rear와 front가 같으면 큐가 비어 있다고 판단하고 TRUE를 반환한다.

  • Boolean IsEmpty_q(Queue queue): 이 함수는 큐가 비어 있는지 확인한다. rear와 front가 같으면 큐가 비어 있음을 나타내며, 이 경우 TRUE를 반환한다.

큐의 isFull

Boolean IsFull_q(Queue queue, int maxQueueSize) { // 큐가 가득 찼는지 확인하는 IsFull_q 함수 정의
    return ((queue.rear + 1) % queue.capacity == queue.front); // rear 다음 위치가 front와 같으면 TRUE, 아니면 FALSE 반환
}

이 코드는 큐가 가득 찼는지 확인하는 기능을 수행한다. 큐의 rear 다음 위치가 front와 같으면 큐가 가득 찼다고 판단하고 TRUE를 반환한다.

  • Boolean IsFull_q(Queue queue, int maxQueueSize): 이 함수는 큐가 가득 찼는지 확인한다. rear 다음 위치가 front와 같으면 큐가 가득 찼음을 나타내며, 이 경우 TRUE를 반환한다.

배열을 이용한 큐의 구현

큐의 생성

#define QUEUE_SIZE 5 // 큐의 크기를 5로 정의
typedef int Element; // Element라는 이름으로 int 타입 정의
Element queue[QUEUE_SIZE]; // 크기가 QUEUE_SIZE인 배열 queue 선언
int front = 0; // 큐의 front 인덱스를 0으로 초기화
int rear = 0; // 큐의 rear 인덱스를 0으로 초기화

이 코드는 크기가 5인 정수형 큐를 구현한다. queue 배열을 사용하여 큐의 요소들을 저장하며, front와 rear 변수는 큐의 맨 앞과 맨 뒤의 위치를 나타낸다.

  • #define QUEUE_SIZE 5: 큐의 최대 크기를 5로 정의한다.
  • typedef int Element: Element라는 새로운 타입 이름으로 int 타입을 정의한다.
  • Element queue[QUEUE_SIZE]: Element 타입의 배열 queue를 선언하고, 크기는 QUEUE_SIZE(5)이다.
  • int front = 0; int rear = 0;: 큐의 시작(front)과 끝(rear)을 나타내는 인덱스를 0으로 초기화한다.

큐의 삽입

void Add_q(Element item) { // Element 타입의 item을 매개변수로 받는 Add_q 함수 정의
    if (rear == QUEUE_SIZE) { // rear가 QUEUE_SIZE와 같으면, 즉 큐가 꽉 찼으면
        printf("Queue is full!!"); // "Queue is full!!" 출력
        return; // 함수 종료
    } 
    queue[rear++] = item; // 큐의 rear 위치에 item을 삽입하고 rear를 1 증가
}

이 코드는 큐에 새로운 요소를 삽입하는 Add_q 함수를 정의한다. 큐가 꽉 차 있으면 (즉, rear 인덱스가 큐의 최대 크기와 같으면) 오류 메시지를 출력하고 함수를 종료한다. 그렇지 않으면 주어진 요소를 큐의 rear 위치에 삽입하고 rear 인덱스를 1 증가시킨다.

- `void Add_q(Element item)`: `Element` 타입의 아이템을 받아 큐에 추가하는 함수이다.
- `if (rear == QUEUE_SIZE)`: 큐가 꽉 찼는지 확인한다. 꽉 찼으면 오류 메시지를 출력하고 함수를 종료한다.
- `queue[rear++] = item`: 큐의 현재 `rear` 위치에 아이템을 삽입하고 `rear`를 1 증가시킨다.

큐의 삭제

Element Delete_q() { // 큐에서 요소를 삭제하는 함수 Delete_q 정의
    if (front == rear) { // front와 rear가 같으면 큐가 비어있음을 의미
        printf("Queue is empty"); // 큐가 비어있다는 메시지 출력
        return -1; // 오류 값 -1을 반환
    } 
    return queue[front++]; // 큐의 front 위치의 요소를 반환하고 front를 1 증가
}

이 코드는 큐에서 요소를 삭제하는 Delete_q 함수를 정의한다. 큐가 비어 있을 때 (즉, front와 rear가 같을 때) "Queue is empty" 메시지를 출력하고, 오류 값을 -1로 반환한다. 큐가 비어 있지 않으면, 큐의 front 위치에 있는 요소를 반환하고, front를 1 증가시킨다.

  • Element Delete_q(): 이 함수는 큐에서 요소를 삭제하고, 삭제한 요소를 반환한다. 큐가 비어 있으면 오류 메시지를 출력하고, 오류 값을 반환한다. 큐가 비어 있지 않으면 front 위치의 요소를 반환하고, front를 1 증가시킨다. 이 함수는 큐의 데이터 관리 및 처리에 사용된다.

연결 리스트

리스트의 생성

struct linked_list_node { // 연결 리스트 노드 구조체 정의
    int data; // 노드가 저장할 데이터
    struct linked_list_node *link; // 다음 노드를 가리킬 포인터
};

이 코드는 연결 리스트를 위한 기본 노드 구조를 정의한다. 각 노드는 int 타입의 data 필드와 다음 노드를 가리키는 linked_list_node 타입의 포인터 link를 갖는다.

  • struct linked_list_node: 이 구조체는 연결 리스트의 개별 노드를 나타낸다. 각 노드는 데이터를 저장하는 data 필드와 다음 노드를 가리키는 link 포인터를 포함한다.

포인터의 할당과 변환 예

int a, *p_a; // 정수형 변수 a와 정수형 포인터 p_a 선언
float b, *p_b; // 실수형 변수 b와 실수형 포인터 p_b 선언
p_a = (int *)malloc(sizeof(int)); // 정수형 크기만큼 메모리 할당 후 p_a에 주소 저장
p_b = (float *)malloc(sizeof(float)); // 실수형 크기만큼 메모리 할당 후 p_b에 주소 저장
*p_a = 10; // p_a가 가리키는 메모리에 10 저장
*p_b = 3.14; // p_b가 가리키는 메모리에 3.14 저장
printf("a is %d, b is %f\n", *p_a, *p_b); // p_a와 p_b가 가리키는 값을 출력
free(p_a); // p_a가 가리키는 메모리 해제
free(p_b); // p_b가 가리키는 메모리 해제

이 코드는 동적 메모리 할당을 사용하여 정수형과 실수형 포인터에 메모리를 할당하고, 이 메모리에 값을 저장한 다음 출력하는 예제이다. 마지막으로 할당된 메모리를 해제하여 메모리 누수를 방지한다.

  • 동적 메모리 할당: malloc 함수를 사용하여 각 타입(int, float)에 필요한 만큼의 메모리를 할당한다. malloc은 void* 타입을 반환하므로, 적절한 타입으로 형 변환을 해주어야 한다.
  • 값의 저장과 출력: 할당된 메모리에 * 연산자(역참조 연산자)를 사용하여 값을 저장하고, printf 함수를 통해 저장된 값을 출력한다.
  • 메모리 해제: free 함수를 사용하여 할당된 메모리를 해제한다. 이는 메모리 누수를 방지하는 중요한 단계이다.

연결 리스트의 생성

typedef struct ListNode { // 단순 연결 리스트의 노드 구조 정의
    int data; // 데이터를 저장하는 변수
    struct ListNode* link; // 다음 노드를 가리키는 포인터
} listNode;

typedef struct { // 리스트의 헤드(첫 번째) 노드 구조 정의
    listNode* head; // 헤드 노드를 가리키는 포인터
} linkedList_h;

linkedList_h* createLinkedList(void) { // 연결 리스트 생성 함수
    linkedList_h* H; // 리스트를 가리키는 포인터 H 선언
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // 리스트의 헤드 노드에 대한 메모리 할당
    H->head = NULL; // 헤드 노드 초기화(빈 리스트)
    return H; // 리스트의 헤드 포인터 반환
}

이 코드는 단순 연결 리스트를 생성하는 기능을 수행한다. ListNode 구조체는 각 노드의 데이터와 다음 노드를 가리키는 포인터를 포함한다. linkedList_h 구조체는 연결 리스트의 첫 번째 노드인 헤드 노드를 가리킨다. createLinkedList 함수는 새로운 연결 리스트를 생성하고, 빈 리스트(헤드 노드가 NULL)를 반환한다.

연결 리스트의 노드 삽입

void addNode(linkedList_h* H, int x) { // 리스트 마지막 노드에 삽입 연산, x값은 삽입할 데이터
    listNode* NewNode; // 새로운 노드를 위한 포인터 선언
    listNode* LastNode; // 마지막 노드를 찾기 위한 포인터 선언
    NewNode = (listNode*)malloc(sizeof(listNode)); // 새 노드에 대한 메모리 할당
    NewNode->data = x; // 새 노드에 데이터 할당
    NewNode->link = NULL; // 새 노드의 다음 링크를 NULL로 초기화

    if (H->head == NULL) { // 현재 리스트가 비어있는 경우
        H->head = NewNode; // 헤드 노드로 새 노드 설정
        return;
    }
    LastNode = H->head; // 마지막 노드 찾기 시작
    while(LastNode->link != NULL) // 마지막 노드를 찾을 때까지 반복
        LastNode = LastNode->link; // 다음 노드로 이동
    LastNode->link = NewNode; // 마지막 노드의 다음으로 새 노드 연결
}

이 코드는 연결 리스트에 새로운 노드를 추가하는 기능을 수행한다. 새 노드(NewNode)는 주어진 데이터 x를 포함하며, 리스트의 마지막 위치에 삽입된다. 리스트가 비어 있으면 새 노드가 헤드 노드가 된다. 그렇지 않으면 기존의 마지막 노드(LastNode)를 찾아 그 다음 노드로 새 노드를 연결한다.

연결 리스트의 헤드에 노드 삽입 (빈 연결리스트의 경우)

void addAfterNode(linkedList_h* H, listNode* prevNode, int newData) { // 리스트 중간에 새 노드를 삽입하는 함수 정의
    listNode* NewNode; // 새 노드 포인터 선언
    NewNode = (listNode*)malloc(sizeof(listNode)); // 새 노드에 메모리 할당
    NewNode->data = newData; // 새 노드의 데이터 필드에 newData 할당
    NewNode->link = prevNode->link; // 새 노드의 링크가 이전 노드의 다음 노드를 가리키게 함
    prevNode->link = NewNode; // 이전 노드의 링크가 새 노드를 가리키게 함
}

이 코드는 연결 리스트의 주어진 노드(prevNode) 뒤에 새 노드(NewNode)를 삽입하는 기능을 수행한다. 새 노드에는 전달된 데이터(newData)가 저장되며, 삽입 후 새 노드는 이전 노드의 다음 노드를 가리키고, 이전 노드는 새 노드를 가리킨다.

연결 리스트 뒤에 한 개의 노드 삽입

void addNode(linkedList_h* H, int x) { // 연결 리스트의 끝에 새 노드를 삽입하는 함수 정의
    listNode* NewNode; // 새 노드 포인터 선언
    listNode* LastNode; // 마지막 노드를 가리킬 포인터 선언
    NewNode = (listNode*)malloc(sizeof(listNode)); // 새 노드에 메모리 할당
    NewNode->data = x; // 새 노드의 데이터 필드에 x 할당
    NewNode->link = NULL; // 새 노드의 링크를 NULL로 초기화 (노드의 끝을 나타냄)
    if(H->head == NULL) { // 리스트가 비어있는 경우
        H->head = NewNode; // 헤드가 새 노드를 가리키게 함
        return;
    }
    LastNode = H->head; // LastNode를 리스트의 헤드로 초기화
    while(LastNode->link != NULL) { // 마지막 노드를 찾을 때까지 반복
        LastNode = LastNode->link; // 다음 노드로 이동
    }
    LastNode->link = NewNode; // 마지막 노드의 링크가 새 노드를 가리키게 함
}

이 코드는 연결 리스트의 끝에 새 노드를 삽입하는 기능을 수행한다. 새 노드에는 전달된 데이터(x)가 저장되고, 리스트가 비어있는 경우 새 노드가 리스트의 헤드가 된다. 리스트에 이미 노드가 있는 경우, 마지막 노드를 찾고, 그 노드의 링크를 새 노드에 연결한다.

연결 리스트 뒤에 한 개의 노드 삽입

LastNode = H->head; // H의 head로 시작하여 마지막 노드를 찾는다.
while(LastNode->link != NULL) // 마지막 노드까지 반복
    LastNode = LastNode->link; // 다음 노드로 이동
LastNode->link = NewNode; // 마지막 노드의 link를 새 노드로 설정

이 코드는 연결 리스트의 마지막 노드를 찾아 그 뒤에 새로운 노드(NewNode)를 삽입하는 작업을 수행한다. H->head에서 시작하여 리스트의 마지막 노드(LastNode)를 찾고, LastNode의 link 필드를 NewNode로 설정하여 새 노드를 연결 리스트의 맨 끝에 추가한다.

연결 리스트의 특정 노드 뒤에 새 노드의 삽입 연산

void addNode(linkedList_h* H, listNode* prevNode, int newData) {
    listNode* NewNode; // 새로운 노드를 위한 포인터 선언
    NewNode = (listNode*)malloc(sizeof(listNode)); // 새 노드를 위한 메모리 할당
    NewNode->data = newData; // 새 노드의 데이터 필드에 newData 저장
    NewNode->link = NULL; // 새 노드의 link 초기화
    NewNode->link = prevNode->link; // 새 노드의 link를 prevNode의 다음 노드로 설정
    prevNode->link = NewNode; // prevNode의 link를 새 노드로 설정
    return;
}

이 함수는 연결 리스트 H에서 특정 노드 prevNode 뒤에 새로운 노드를 삽입하는 연산을 수행한다. 새 노드(NewNode)는 newData 값을 데이터 필드에 저장하며, prevNode의 다음 노드로 연결된다. 이 연산은 prevNode 다음에 새로운 노드를 추가하여 리스트를 확장한다.

연결 리스트의 특정 노드 뒤에 새 노드의 삽입 연산

NewNode->link = prevNode->link; // 새 노드의 link를 prevNode의 다음 노드로 설정
prevNode->link = NewNode; // prevNode의 link를 새 노드로 설정

이 부분의 코드는 연결 리스트에서 prevNode 뒤에 NewNode를 삽입하는 과정을 구체적으로 보여준다. 먼저, NewNode의 link를 prevNode의 다음 노드로 설정한 후, prevNode의 link를 NewNode로 설정하여 새 노드를 연결한다. 이 과정을 통해 연결 리스트에 새로운 노드가 추가된다.

연결 리스트의 마지막 노드 삭제

void deleteLastNode(linkedList_h* H) { // 연결 리스트의 마지막 노드를 삭제하는 함수 정의
    listNode* prevNode; // 이전 노드를 가리킬 포인터 변수 선언
    listNode* delNode; // 삭제할 노드를 가리킬 포인터 변수 선언

    if(H->head == NULL) 
        return; // 리스트가 비어있는 경우, 즉 head가 NULL인 경우 아무 작업도 수행하지 않고 반환

    if(H->head->link == NULL) { // 리스트에 노드가 하나만 있는 경우
        free(H->head); // head가 가리키는 노드 메모리 해제
        H->head = NULL; // head를 NULL로 설정하여 리스트를 공백 상태로 만듦
        return;
    } else { // 리스트에 노드가 두 개 이상 있는 경우
        prevNode = H->head; // prevNode를 리스트의 첫 번째 노드로 설정
        delNode = H->head->link; // delNode를 두 번째 노드로 설정
        while(delNode->link != NULL) { // delNode의 link가 NULL이 될 때까지, 즉 마지막 노드에 도달할 때까지 반복
            prevNode = delNode; // prevNode를 delNode로 이동
            delNode = delNode->link; // delNode를 다음 노드로 이동
        }
        free(delNode); // 마지막 노드 메모리 해제
        prevNode->link = NULL; // prevNode의 link를 NULL로 설정하여 마지막 노드를 삭제
    }
}

이 코드는 연결 리스트에서 마지막 노드를 삭제하는 함수 deleteLastNode를 정의한다. 리스트가 비어있거나 노드가 하나만 있는 경우 간단히 처리하고, 두 개 이상의 노드가 있는 경우 마지막 노드까지 순회하여 마지막 노드를 삭제한다. 이 과정에서 마지막 노드 이전의 노드(prevNode)를 추적하여 마지막 노드를 삭제한 후 prevNode의 링크를 NULL로 설정한다. 이 함수는 연결 리스트의 끝 부분에서 노드를 제거하는 작업에 사용된다.

연결 리스트의 마지막 노드 삭제 - 리스트에 노드가 한 개인 경우

if(H->head->link == NULL) { // 리스트의 헤드 노드가 마지막 노드인 경우
    free(H->head); // 헤드 노드 메모리 해제
    H->head = NULL; // 헤드 포인터를 NULL로 설정
    return; // 함수 종료
}

이 코드는 연결 리스트에서 노드가 하나만 있을 때, 그 노드를 삭제하는 작업을 수행한다. 리스트의 헤드 노드가 마지막 노드인 경우, 해당 노드를 메모리에서 해제하고 헤드 포인터를 NULL로 설정한다.

  • if(H->head->link == NULL): 이 조건문은 연결 리스트에 노드가 하나만 있는지 확인한다. 만약 그렇다면, 해당 노드를 메모리에서 해제하고 리스트를 비워준다.

연결 리스트의 마지막 노드 삭제 - 연결 리스트에 노드가 여러 개인 경우

else {
    prevNode = H->head; // 이전 노드를 헤드로 설정
    delNode = H->head->link; // 삭제할 노드를 헤드 다음 노드로 설정
    while(delNode->link != NULL) { // 마지막 노드까지 이동
        prevNode = delNode; // 이전 노드를 현재 노드로 업데이트
        delNode = delNode->link; // 다음 노드로 이동
    }
    free(delNode); // 마지막 노드 메모리 해제
    prevNode->link = NULL; // 이전 노드의 링크를 NULL로 설정
}

이 코드는 연결 리스트에 여러 개의 노드가 있을 때 마지막 노드를 삭제하는 작업을 수행한다. 리스트의 마지막 노드를 찾아서 메모리에서 해제하고, 그 전 노드의 링크를 NULL로 설정하여 리스트의 끝을 표시한다.

  • else: 이 부분은 연결 리스트에 노드가 여러 개 있는 경우를 처리한다. 마지막 노드를 찾아서 삭제하고, 그 전 노드의 링크를 NULL로 설정한다.

마지막 노드가 삭제된 모습

else {
    prevNode = H->head; // head부터 시작하여 이전 노드를 가리킴
    delNode = H->head->link; // head 다음 노드부터 삭제할 노드를 가리킴
    while(delNode->link != NULL) { // 마지막 노드에 도달할 때까지 반복
        prevNode = delNode; // 현재 노드를 이전 노드로 갱신
        delNode = delNode->link; // 다음 노드로 이동
    }
    free(delNode); // 마지막 노드 메모리 해제
    prevNode->link = NULL; // 이전 노드의 링크를 NULL로 설정하여 리스트의 마지막을 표시
}

이 코드는 연결 리스트에서 마지막 노드를 삭제하는 로직을 구현한다. H->head를 시작으로 delNode를 이용해 리스트를 순회하며 마지막 노드에 도달한다. 마지막 노드에 도달하면 free(delNode)를 호출하여 해당 노드를 메모리에서 해제하고, prevNode의 link를 NULL로 설정하여 리스트의 끝을 나타낸다. 이 과정은 연결 리스트에서 마지막 노드를 제거할 때 사용된다.

연결 리스트의 특정 노드 검색

void findAndDeleteNode(linkedList_h* H, int targetData) { // 연결 리스트 H에서 특정 데이터(targetData)를 가진 노드를 검색하여 삭제하는 함수 정의
    listNode* prevNode; // 이전 노드를 가리킬 포인터 prevNode 선언
    listNode* delNode; // 삭제할 노드를 가리킬 포인터 delNode 선언
    if(H->head == NULL) return; // 리스트가 비어있는 경우 함수 종료

    prevNode = H->head; // prevNode를 리스트의 첫 번째 노드로 설정
    delNode = H->head; // delNode를 리스트의 첫 번째 노드로 설정
    while(delNode != NULL) { // delNode가 NULL이 아닐 때까지 반복
        if(delNode->data == targetData) { // delNode의 데이터가 targetData와 일치하는 경우
            if(delNode == H->head) { // 삭제할 노드가 리스트의 첫 번째 노드인 경우
                H->head = delNode->link; // 리스트의 헤드를 delNode의 다음 노드로 변경
            } else {
                prevNode->link = delNode->link; // prevNode의 링크를 delNode의 다음 노드로 변경
            }
            free(delNode); // delNode 메모리 해제
            return;
        } else {
            prevNode = delNode; // prevNode를 현재 delNode로 설정
            delNode = delNode->link; // delNode를 다음 노드로 이동
        }
    }
}

이 코드는 연결 리스트에서 주어진 데이터(targetData)를 가진 노드를 찾아 삭제하는 기능을 수행한다. 먼저 리스트가 비어있는지 확인하고, 비어있지 않다면 리스트를 순회하면서 주어진 데이터를 가진 노드를 찾는다. 해당 노드를 찾으면, 이전 노드의 링크를 현재 노드의 다음 노드로 연결하고, 현재 노드를 메모리에서 해제한다. 만약 삭제할 노드가 리스트의 첫 번째 노드라면, 리스트의 헤드를 두 번째 노드로 변경한다.

연결 리스트의 특정 노드 삭제

void deleteNode(linkedList_h* H, listNode* prevNode, listNode* delNode) { // 연결 리스트에서 특정 노드(delNode)를 삭제하는 함수 정의
    prevNode->link = delNode->link; // prevNode의 link를 delNode의 다음 노드로 설정
    free(delNode); // delNode 메모리 해제
    return; // 함수 종료
}

이 코드는 연결 리스트에서 특정 노드(delNode)를 삭제하는 기능을 수행한다. deleteNode 함수는 연결 리스트(linkedList_h* H), 삭제 전 노드(listNode* prevNode), 삭제할 노드(listNode* delNode)를 매개변수로 받는다. 삭제 과정에서 prevNode의 링크를 delNode의 다음 노드로 재지정하고, delNode는 메모리에서 해제된다.

  • void deleteNode(linkedList_h* H, listNode* prevNode, listNode* delNode): 이 함수는 연결 리스트에서 특정 노드(delNode)를 삭제한다. 삭제할 노드의 이전 노드(prevNode)의 링크를 삭제할 노드의 다음 노드로 재설정하고, 삭제할 노드는 메모리에서 해제한다. 이 함수는 리스트의 중간이나 끝부분에 있는 노드를 삭제할 때 사용된다.

delNode의 다음 노드를 가리키는 prevNode의 모습

void deleteAfterNode(linkedList_h* H, listNode* prevNode, listNode* delNode) {
    prevNode->link = delNode->link; // prevNode의 link를 delNode의 다음 노드로 설정
    free(delNode); // delNode 메모리 해제
    return; // 함수 종료
}

이 코드는 deleteNode 함수와 동일한 기능을 수행하지만, 함수의 이름이 deleteAfterNode로 다르게 표현되어 있다. 이 함수는 prevNode의 링크를 delNode의 다음 노드로 재설정하고, delNode는 메모리에서 해제된다. 이 함수는 prevNode가 가리키는 노드의 다음 노드(delNode)를 삭제할 때 사용된다.

원형 연결 리스트의 생성

typedef struct ListNode { // 원형 연결 리스트의 노드 구조를 정의하는 구조체
    int data; // 데이터 필드
    struct ListNode* link; // 다음 노드를 가리키는 링크 필드
} listNode;

typedef struct { // 원형 연결 리스트의 헤드 노드 구조를 정의하는 구조체
    listNode* head; // 첫 번째 노드를 가리키는 헤드 포인터
} linkedList_h;

linkedList_h* createLinkedList_h(void) { // 원형 연결 리스트를 생성하고 초기화하는 함수
    linkedList_h* H; // 헤드 노드 포인터 H 선언
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // 헤드 노드에 대한 메모리 할당
    H->head = NULL; // 헤드 노드의 head 필드를 NULL로 초기화
    return H; // 초기화된 리스트의 헤드 노드 포인터 반환
}

이 코드는 원형 연결 리스트를 생성하고 초기화하는 기능을 수행한다. listNode 구조체는 각 노드의 데이터와 링크를 정의하고, linkedList_h 구조체는 리스트의 헤드 노드를 정의한다. createLinkedList_h 함수는 새로운 원형 연결 리스트의 헤드 노드를 메모리에 할당하고, 초기화하여 반환한다.

원형 연결 리스트의 노드 삽입

void addFirstNode(linkedList_h* H, int x) { // 원형 연결 리스트의 첫 번째 위치에 노드를 삽입하는 함수
    listNode* newNode; // 새로운 노드 포인터 newNode 선언
    newNode = (listNode*)malloc(sizeof(listNode)); // 새 노드에 대한 메모리 할당
    newNode->data = x; // 새 노드의 데이터 필드에 x 할당
    newNode->link = NULL; // 새 노드의 링크 필드를 NULL로 초기화

    if (H->head == NULL) { // 리스트가 비어있는 경우
        H->head = newNode; // 헤드 노드의 head 필드를 새 노드로 설정
        newNode->link = newNode; // 새 노드의 링크를 자기 자신으로 설정 (원형 연결)
    } else { // 리스트에 이미 노드가 있는 경우
        listNode* tempNode = H->head; // 임시 노드 포인터 tempNode를 헤드 노드로 초기화
        while(tempNode->link != H->head) { // 리스트의 마지막 노드까지 순회
            tempNode = tempNode->link; // 다음 노드로 이동
        }
        newNode->link = H->head; // 새 노드의 링크를 헤드 노드로 설정
        tempNode->link = newNode; // 마지막 노드의 링크를 새 노드로 설정
    }
}

이 코드는 원형 연결 리스트의 첫 번째 위치에 새로운 노드를 삽입하는 기능을 수행한다. 리스트가 비어있는 경우와 이미 노드가 있는 경우를 구분하여 처리한다. 비어있는 경우에는 새 노드를 헤드 노드로 설정하고, 이미 노드가 있는 경우에는 마지막 노드를 찾아 그 노드의 링크를 새 노드로 설정한다.

원형 연결 리스트의 첫 번째 노드 삽입의 최종 결과

if (H->head == NULL) { // 현재 원형 연결 리스트가 공백인 경우
    H->head = NewNode; // 새 노드를 헤드로 설정
    NewNode->link = NewNode; // 새 노드의 링크가 자기 자신을 가리키게 함
    return;
} else { // 현재 리스트가 공백이 아닌 경우
    listNode* tempNode = H->head; // 헤드 노드부터 시작
    while(tempNode->link != H->head) { // 리스트 끝까지 순회
        tempNode = tempNode->link; // 다음 노드로 이동
    }
    NewNode->link = H->head; // 새 노드의 링크가 헤드 노드를 가리키게 함
    tempNode->link = NewNode; // 마지막 노드의 링크가 새 노드를 가리키게 함
}

이 코드는 원형 연결 리스트에 새 노드를 삽입하는 과정을 나타낸다. 원형 연결 리스트가 비어 있으면 새 노드를 헤드로 설정하고, 그렇지 않으면 리스트의 마지막 노드까지 이동하여 새 노드를 연결한다. 새 노드는 항상 헤드 노드를 가리키게 설정되며, 마지막 노드는 새 노드를 가리키도록 변경된다.

첫 번째 노드를 가리키는 tempNode의 모습

listNode* tempNode = H->head; // 헤드 노드부터 시작
while(tempNode->link != H->head) { // 리스트 끝까지 순회
    tempNode = tempNode->link; // 다음 노드로 이동
}
NewNode->link = H->head; // 새 노드의 링크가 헤드 노드를 가리키게 함
tempNode->link = NewNode; // 마지막 노드의 링크가 새 노드를 가리키게 함

이 코드 부분은 원형 연결 리스트에서 마지막 노드를 찾아 새 노드를 삽입하는 과정을 보여준다. tempNode는 리스트의 마지막 노드를 찾기 위해 사용되며, 마지막 노드에 도달하면 새 노드를 연결한다.

첫 번째 노드를 가리키는 newNode의 모습

NewNode->link = H->head; // 새로운 노드의 link가 헤드 노드를 가리키게 함

이 코드는 새로 삽입되는 노드(NewNode)의 link 필드를 헤드 노드(H->head)로 설정하여, 새 노드가 리스트의 첫 번째 노드를 가리키도록 하는 것을 나타낸다. 이는 원형 연결 리스트의 특성상, 새 노드가 리스트의 마지막 노드가 되면서 동시에 다시 첫 번째 노드(헤드 노드)를 가리키도록 해야 하기 때문이다.

마지막 노드가 첫 번째 노드를 가리키는 모습

listNode* tempNode = H->head; // H의 head부터 시작하는 tempNode 포인터 선언
while(tempNode->link != H->head) { // tempNode의 link가 H의 head를 가리키지 않을 때까지 반복
    tempNode = tempNode->link; // tempNode를 다음 노드로 이동
}
tempNode->link = NewNode; // 마지막 노드의 link가 새로운 노드를 가리키게 함

이 코드는 원형 연결 리스트에서 마지막 노드를 찾아 그 노드의 link가 새로운 노드 NewNode를 가리키도록 설정하는 과정이다. 원형 연결 리스트에서는 마지막 노드의 link가 리스트의 처음으로 돌아가기 때문에, H->head를 가리키지 않을 때까지 반복하여 마지막 노드를 찾는다.

원형 연결 리스트의 중간 위치에 노드를 삽입

void addMiddleNode(linkedList_h* H, listNode* prevNode, int itdata) {
    listNode* NewNode; // 새로운 노드 포인터 NewNode 선언
    NewNode = (listNode*)malloc(sizeof(listNode)); // NewNode에 대한 메모리 할당
    NewNode->data = itdata; // NewNode의 데이터 필드에 itdata 저장
    NewNode->link = prevNode->link; // NewNode의 link가 prevNode 다음 노드를 가리키도록 설정
    prevNode->link = NewNode; // prevNode의 link가 NewNode를 가리키게 설정
}

이 코드는 원형 연결 리스트에 중간 위치에 새 노드를 삽입하는 함수 addMiddleNode를 정의한다. 이 함수는 새 노드 NewNode를 생성하고, 그 노드에 데이터를 저장한 다음, prevNode 다음에 이 노드를 삽입한다. prevNode의 link가 NewNode를 가리키게 하고, NewNode의 link는 prevNode가 이전에 가리키던 노드를 가리키도록 설정된다. 이렇게 함으로써, 리스트의 연결성을 유지하면서 새 노드를 삽입한다.

새롭게 생성된 노드의 모습

listNode* NewNode;                     // listNode 타입의 포인터 NewNode 선언
NewNode = (listNode*)malloc(sizeof(listNode)); // 새 노드에 대한 메모리 할당
NewNode->data = itdata;                // NewNode의 data 필드에 itdata 할당
NewNode->link = NULL;                  // NewNode의 link 필드를 NULL로 초기화

이 코드는 새로운 노드를 생성하고, 해당 노드의 data 필드에 itdata 값을 할당한 다음, link 필드를 NULL로 초기화하는 과정을 보여준다. malloc 함수를 사용하여 listNode 크기의 메모리를 동적으로 할당하고, 이를 NewNode 포인터에 연결한다.

newNode의 링크 값이 변경된 모습

NewNode->link = prevNode->link; // NewNode의 link 필드를 prevNode의 link 값으로 설정
prevNode->link = NewNode;       // prevNode의 link 필드를 NewNode로 설정

이 코드는 새로 생성된 노드 NewNode를 연결 리스트에 삽입하는 과정을 보여준다. NewNode의 link 필드는 prevNode의 현재 link 값으로 설정되고, prevNode의 link 필드는 NewNode로 업데이트된다. 이로써 NewNode는 prevNode 뒤에 연결되며, prevNode 다음 노드로 연결된다.

prevNode의 링크 값이 변경된 모습

prevNode->link = NewNode; // prevNode의 link 필드를 NewNode로 설정

이 코드 조각은 연결 리스트에서 prevNode 다음에 NewNode를 삽입하는 부분을 나타낸다. prevNode의 link 필드는 새로 생성된 노드 NewNode를 가리키도록 설정된다. 이는 prevNode와 NewNode 간의 연결을 구성하여 리스트에 새 노드를 추가하는 기본적인 과정이다.

원형 연결 리스트의 노드 삭제를 위한 탐색

void findDelCircularNode(linkedList_h* H, int targetData) { // 원형 연결 리스트 H에서 targetData를 찾아 삭제하는 함수 정의
    listNode* tempNode; // 임시 노드 포인터 tempNode 선언
    listNode* prevNode; // 이전 노드를 가리킬 포인터 prevNode 선언
    prevNode = H->head; // prevNode를 리스트의 head로 초기화
    if (H->head == NULL) { // 리스트가 비어있는 경우
        printf("Circular Linked List is EMPTY\n"); // 비어있다는 메시지 출력
        return; // 함수 종료
    } else {
        tempNode = H->head; // tempNode를 리스트의 head로 초기화
        do {
            if (tempNode->data == targetData) { // tempNode의 데이터가 targetData와 같은 경우
                return deleteCircularNode(H, prevNode); // 해당 노드 삭제 함수 호출
            } else {
                prevNode = tempNode; // prevNode를 tempNode로 업데이트
                tempNode = tempNode->link; // tempNode를 다음 노드로 이동
            }
        } while (tempNode != H->head); // 리스트의 끝(head로 돌아올 때까지)까지 반복
    }
    printf("Search Fail\n"); // 원하는 데이터를 찾지 못했을 때 메시지 출력
    return; // 함수 종료
}

이 코드는 원형 연결 리스트에서 특정 데이터를 가진 노드를 찾아 삭제하는 기능을 수행한다. 리스트가 비어있지 않은 경우, 첫 번째 노드부터 시작하여 리스트를 순회하며 데이터를 검색한다. 검색된 데이터가 타겟 데이터와 일치하면 해당 노드를 삭제하는 deleteCircularNode 함수를 호출한다. 만약 리스트 전체를 순회했음에도 불구하고 해당 데이터를 찾지 못하면 "Search Fail" 메시지를 출력하고 함수를 종료한다.

tempNode와 prevNode가 이동한 모습

else {
    tempNode = H->head; // 원형 연결 리스트의 첫 번째 노드로 tempNode를 초기화
    do {
        if (tempNode->data == itdata) { // tempNode의 데이터가 itdata와 같은 경우
            return deleteCircularNode(H, prevNode); // deleteCircularNode 함수를 호출하여 노드 삭제
        } else {
            prevNode = tempNode; // prevNode를 현재 tempNode로 업데이트
            tempNode = tempNode->link; // tempNode를 다음 노드로 이동
        }
    } while (tempNode != H->head); // tempNode가 다시 head에 도달할 때까지 반복
}

이 코드는 원형 연결 리스트에서 특정 데이터 값을 갖는 노드를 찾아 삭제하는 과정을 보여준다. tempNode는 리스트를 탐색하는 동안 현재 노드를 가리키고, prevNode는 tempNode의 바로 이전 노드를 가리킨다. itdata 값과 일치하는 노드를 찾으면 해당 노드를 삭제한다.

  • else 블록: 이 코드 블록은 주어진 조건이 거짓일 때 실행된다. 여기서는 itdata 값을 갖는 노드를 찾아 삭제하는 과정을 수행한다.
  • tempNode = H->head: 원형 연결 리스트의 시작점(헤드)에서 탐색을 시작한다.
  • do-while 루프: 리스트를 순회하며 조건에 맞는 노드를 찾는다.
  • if (tempNode->data == itdata): 찾고자 하는 데이터 값을 갖는 노드를 찾았을 때의 처리를 정의한다.
  • return deleteCircularNode(H, prevNode): 조건에 맞는 노드를 찾았으면 삭제 함수를 호출하고 탐색을 종료한다.

원형 연결 리스트의 검색 실패 예

else {
    tempNode = H->head; // 첫 번째 노드부터 검색 시작
    do {
        if(tempNode->data == targetData) { // 찾고자 하는 데이터 값이 있는지 확인
            return deleteCircularNode(H, prevNode); // 데이터가 일치하면 해당 노드 삭제
        }
        else {
            prevNode = tempNode; // prevNode를 현재 노드로 업데이트
            tempNode = tempNode->link; // tempNode를 다음 노드로 이동
        }
    } while(tempNode != H->head); // 리스트의 끝(헤드)에 도달할 때까지 반복
} // 검색과 삭제 과정 완료

이 코드는 원형 연결 리스트에서 특정 값을 갖는 노드를 찾고, 그 노드를 삭제하는 기능을 수행한다. 노드의 데이터가 targetData와 일치하면 deleteCircularNode 함수를 호출하여 해당 노드를 삭제한다.

  • else: if 문에 해당되지 않는 경우, 이 블록이 실행된다.
  • tempNode = H->head: 탐색을 시작하기 위해 tempNode를 리스트의 첫 번째 노드로 설정한다.
  • do-while 루프: 리스트 전체를 순회하며 특정 데이터 값을 찾는다.
  • if(tempNode->data == targetData): 찾고자 하는 데이터 값을 갖는 노드를 찾았을 때의 처리를 정의한다.

원형 연결 리스트의 삭제

void deleteCircularNode(linkedList_h* H, listNode* prevNode) {
    listNode* delNode; // 삭제할 노드를 가리킬 포인터
    if(prevNode->link == H->head) { // 삭제할 노드가 head인 경우
        delNode = H->head;

 // delNode를 head로 설정
        if(H->head->link == H->head) { // 리스트에 노드가 하나만 있는 경우
            H->head = NULL; // head를 NULL로 설정
        } else {
            prevNode->link = delNode->link; // prevNode의 링크를 delNode의 다음 노드로 변경
            H->head = delNode->link; // head를 delNode의 다음 노드로 변경
        }
    } else { // 일반적인 경우
        delNode = prevNode->link; // 삭제할 노드를 설정
        prevNode->link = delNode->link; // prevNode의 링크를 변경
    }
    free(delNode); // delNode 메모리 해제
}

이 코드는 원형 연결 리스트에서 특정 노드를 삭제하는 함수 deleteCircularNode를 정의한다. 삭제할 노드가 리스트의 헤드인 경우와 아닌 경우로 나누어 처리하며, 삭제 작업 후에는 노드의 메모리를 해제한다.

  • void deleteCircularNode(...): 특정 노드를 삭제하는 함수를 정의한다.
  • listNode* delNode: 삭제할 노드를 가리키는 포인터를 선언한다.
  • if(prevNode->link == H->head): 삭제할 노드가 head인 경우와 아닌 경우를 구분하여 처리한다.
  • free(delNode): 삭제한 노드의 메모리를 해제한다.

이중 연결 리스트의 정의 및 생성

typedef struct ListNode { 
    struct ListNode* Llink; // 왼쪽 노드를 가리키는 포인터
    int data;               // 노드의 데이터를 저장하는 정수형 변수
    struct ListNode* Rlink; // 오른쪽 노드를 가리키는 포인터
} listNode;

typedef struct {
    listNode* Lhead; // 리스트의 왼쪽 끝 노드를 가리키는 포인터
    listNode* Rhead; // 리스트의 오른쪽 끝 노드를 가리키는 포인터
} linkedList_h;

linkedList_h* createLinkedList_h(void) {
    linkedList_h* H;
    H = (linkedList_h*)malloc(sizeof(linkedList_h)); // linkedList_h 크기만큼의 메모리 할당
    H->Lhead = NULL; // 리스트의 왼쪽 끝을 NULL로 초기화
    H->Rhead = NULL; // 리스트의 오른쪽 끝을 NULL로 초기화
    return H; // 생성된 리스트의 헤드 반환
}

이 코드는 이중 연결 리스트를 정의하고 생성하는 과정을 나타낸다. ListNode 구조체는 각 노드의 데이터와 양쪽 노드를 가리키는 포인터를 가진다. linkedList_h 구조체는 이중 연결 리스트의 양쪽 끝을 가리키는 헤드 포인터들을 포함한다. createLinkedList_h 함수는 새로운 이중 연결 리스트를 생성하고 그 헤드를 반환한다.

  • typedef struct ListNode: 노드의 구조를 정의한다. 각 노드는 왼쪽 링크, 데이터, 오른쪽 링크를 포함한다.
  • typedef struct linkedList_h: 이중 연결 리스트의 헤드 노드 구조를 정의한다. 왼쪽과 오른쪽 끝 노드를 가리키는 포인터를 포함한다.
  • linkedList_h* createLinkedList_h(): 새로운 이중 연결 리스트를 생성하고, 그 헤드 노드를 반환한다.

이중 연결 리스트의 노드 삽입

void addDNode(linkedList_h* H, listNode* prevNode, int x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode)); // 새로운 노드에 대한 메모리 할당
    newNode->Llink = NULL; // 새 노드의 왼쪽 링크를 NULL로 초기화
    newNode->data = x;     // 새 노드의 데이터 필드에 x값을 할당
    newNode->Rlink = NULL; // 새 노드의 오른쪽 링크를 NULL로 초기화

    if(H->Rhead == NULL) { // 리스트가 비어있는 경우
        H->Lhead = newNode; // 새 노드를 리스트의 왼쪽 끝으로 설정
        H->Rhead = newNode; // 새 노드를 리스트의 오른쪽 끝으로 설정
    } else { // 리스트에 노드가 있는 경우
        newNode->Rlink = prevNode->Rlink; // 새 노드의 오른쪽 링크를 이전 노드의 오른쪽 링크로 설정
        prevNode->Rlink = newNode;        // 이전 노드의 오른쪽 링크를 새 노드로 설정
        newNode->Llink = prevNode;        // 새 노드의 왼쪽 링크를 이전 노드로 설정
        if(newNode->Rlink != NULL) {      // 새 노드의 오른쪽 링크가 NULL이 아닌 경우
            newNode->Rlink->Llink = newNode; // 새 노드 오른

쪽의 노드의 왼쪽 링크를 새 노드로 설정
        }
        if(prevNode == H->Rhead) { // 새 노드가 리스트의 오른쪽 끝에 삽입되는 경우
            H->Rhead = newNode;    // 새 노드를 리스트의 오른쪽 끝으로 설정
        }
    }
}

이 코드는 이중 연결 리스트에 새 노드를 삽입하는 과정을 나타낸다. 새 노드는 주어진 데이터 x를 포함하며, 리스트가 비어 있으면 새 노드를 리스트의 양쪽 끝으로 설정한다. 리스트에 노드가 있으면, prevNode 다음에 새 노드를 삽입한다. 삽입 후에는 새 노드와 주변 노드의 링크를 적절히 조정한다.

  • void addDNode(linkedList_h* H, listNode* prevNode, int x): 이 함수는 H가 가리키는 이중 연결 리스트에 새 노드를 삽입한다. 삽입 위치는 prevNode 다음이다.

NewNode가 삽입되어야 할 위치 모습

void deleteDNode(linkedList_h* H, listNode* delNode) {
    if(delNode == H->Lhead && delNode == H->Rhead) { // 리스트에 노드가 하나만 있는 경우
        H->Lhead = NULL; // 리스트의 왼쪽 끝 노드를 NULL로 설정
        H->Rhead = NULL; // 리스트의 오른쪽 끝 노드를 NULL로 설정
    } else {
        if(delNode == H->Lhead) { // 삭제할 노드가 왼쪽 끝 노드인 경우
            H->Lhead = delNode->Rlink; // 왼쪽 끝 노드를 삭제 노드의 오른쪽 링크로 업데이트
        } else {
            delNode->Llink->Rlink = delNode->Rlink; // 삭제 노드의 왼쪽 노드의 오른쪽 링크를 삭제 노드의 오른쪽 노드로 설정
        }
        if(delNode == H->Rhead) { // 삭제할 노드가 오른쪽 끝 노드인 경우
            H->Rhead = delNode->Llink; // 오른쪽 끝 노드를 삭제 노드의 왼쪽 링크로 업데이트
        } else {
            delNode->Rlink->Llink = delNode->Llink; // 삭제 노드의 오른쪽 노드의 왼쪽 링크를 삭제 노드의 왼쪽 노드로 설정
        }
    }
    free(delNode); // 메모리 해제
}

이중 연결 리스트의 특정 노드 삭제

void deleteDNode(linkedList_h* H, listNode* delNode) {
    // 이중 연결 리스트에서 데이터의 값이 300인 노드(delNode)를 삭제하는 연산
    if(delNode->Llink != NULL) {
        delNode->Llink->Rlink = delNode->Rlink; // delNode의 왼쪽 노드의 오른쪽 링크를 delNode의 오른쪽 노드로 설정
    } else {
        H->Lhead = delNode->Rlink; // delNode가 왼쪽 끝 노드인 경우, Lhead를 delNode의 오른쪽 노드로 업데이트
    }

    if(delNode->Rlink != NULL) {
        delNode->Rlink->Llink = delNode->Llink; // delNode의 오른쪽 노드의 왼쪽 링크를 delNode의 왼쪽 노드로 설정
    } else {
        H->Rhead = delNode->Llink; // delNode가 오른쪽 끝 노드인 경우, Rhead를 delNode의 왼쪽 노드로 업데이트
    }

    free(delNode); // 메모리 해제
}

이 코드들은 이중 연결 리스트에서 특정 노드(delNode)를 안전하게 삭제하는 기능을 수행한다. 삭제 과정에서 해당 노드의 이전 노드와 다음 노드의 링크를 적절하게 조정하고, 노드가 리스트의 끝에 위치하는 경우 헤드 노드도 업데이트한다. 삭제된 노드의 메모리는 free 함수를 통해 해제된다. 이 과정은 이중 연결 리스트의 데이터 관리와 메모리 효율성을 유지하는 데 중요하다.

요약 정리

자료 구조란 무엇인가

  • ‘자료’는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)입니다.
  • ‘정보’는 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호 간의 관계(relationship)를 표현하는 내용이라고 할 수 있습니다.
  • ‘정보’는 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 ‘처리 과정’을 거쳐서 정리되고 정돈된 ‘자료’의 2차 처리 결과물이다. 정보는 자료를 처리(process)해서 얻어진 유용한 결과(result)라고 할 수 있습니다.
  • 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하며 추상화를 통해 자료의 논리적 관계를 구조화한 것을 자료구조(data structure)라고 합니다.
  • 알고리즘이란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것 입니다.
  • 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있습니다.
  • 추상화란 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것입니다.
  • 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야할 명령의 추상화입니다.
  • ‘미리 정의된 자료구조’는 프로그래밍 언어를 개발하는 개발자에 의해 정의되고 추상화되었고, 이를 컴퓨터내부에서 프로그래밍 언어의 형태로 구현된 자료구조를 의미합니다.
  • ’미리 정의된 자료구조‘는 프로그래밍 언어 개발자가 프로그램 개발자를 위해 미리 정의하지만, ’사용자 정의 자료구조‘는 프로그램 개발자가 자신의 프로그램 개발 방향에 따라 프로그래밍 언어로 새롭게 정의하여 사용하는 자료구조입니다.
  • 알고리즘이 가지고 있어야 할 조건들 ① 출력, ② 유효성, ③ 입력, ④ 명확성, ⑤ 유한성 등이 있습니다.
  • 알고리즘을 실행하는데 필요한 시간과 공간을 추정하여 알고리즘의 성능을 분석(performance analysis)을 합니다. 그리고 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정하여 알고리즘의의 성능을 측정(performance measurement)합니다.
  • 추상자료형이란 객체의 명세와 그 연산의 명세가 그 객체의 표현과 연산의 구현으로부터 분리된 자료형 , 자료의 복잡한 논리적 성격을 정의하는 형식으로 자료값의 집합과 연산 집합에 대한 명세의 집합

배열

  • 배열은 인덱스와 원소값()의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 갖습니다.
  • 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’를 의미합니다.
  • 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스의 순서(논리적인 순서)와 일치합니다.
  • 배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근(direct access)입니다.
  • 배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정되며, 그 순서에 따라 메인 메모리에서의 저장 위치의 순서가 됩니다.
  • create(n)은 n개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성합니다. 배열을 생성할 때 n개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소값들이 아직은 없다는 것을 의미합니다.
  • 연산 retrieve(a,i)는 배열 a와 인덱스 i를 매개 변수로 전달받아 인덱스 i 위치에 대응되는 원소값 e가 있다면 원소값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환합니다.
  • 연산 store(a, i, e)는 배열 a와 인덱스 i, 원소값 e를 매개 변수로 전달받아 Index를 검사하여 i값이 유효할 경우 쌍이 되게 원소값을 i번째 인덱스에 저장하고 배열 a를 반환합니다.
  • 가장 기본적인 배열은 1차원 배열이며, 한줄짜리 배열을 의미하므로 인덱스는 하나입니다. 한줄짜리 배열은 메모리 영역도 한줄로 할당받습니다.
  • 2차원 배열의 행우선 저장방식은 하나의 행이 모두 연속적으로 메모리 영역을 할당받고, 다음 행이 메모리 영역을 연속적으로 할당받는 방식입니다.
  • 2차원 배열의 열우선 저장방식은 하나의 열이 모두 연속적으로 메모리 영역을 할당받고, 다음 열이 메모리 영역을 연속적으로 할당받는 방식입니다.
  • 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소행렬(sparse matrix)이라 합니다.

스택

  • 스택을 생성하는 연산은 프로그래머가 지정한 크기의 새로운 스택을 생성하는 연산이며, 매개변수인 maxStack은 스택이 저장할 수 있는 최대 개수의 element를 의미합니다.
  • StackIsFull(stack, maxStackSize) 연산은 스택이 가득 찼는지를 확인하며, 저장된 원소의 수가 maxStackSize와 같으면 TRUE(‘스택이 가득 찼다’)를 반환하고 아니면 FALSE(‘스택에 여유 저장 공간이 있다’)를 반환합니다.
  • Stack Push(stack, item) 연산은 스택에 새로운 원소를 삽입합니다. 만일 스택이 가득 찼다(Full)면 더 이상의 원소를 스택에 삽입할 수 없으며, ‘stackFull‘ 메시지를 출력합니다.
  • Boolean StackIsEmpty(stack) 연산은 스택 상태가 빈 상태인지를 확인합니다. 만일 스택이 빈 상태이면 ‘TRUE’ 값을 반환하고, 스택에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
  • Element Pop(stack) 연산자는 스택이 빈 상태라면 삭제할 원소가 없으므로 ‘stackEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 스택의 top이 가리키는 원소를 삭제하고 그 원소를 반환합니다.
  • 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
  • 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형입니다.
  • 중위 표기법(infix notation)은 연산자를 피연산자의 사이에 표기하는 방법이며 일반적으로 가장 많이 사용되는 표기 방법(A+B)입니다.
  • 전위 표기법(prefix notation)은 연산자를 피연산자의 앞에 표기하는 방법 (+AB)입니다.
  • 후위 표기법(postfix notation)은 연산자를 피연산자의 뒤에 표기하는 방법 (AB+)입니다.

큐

  • 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다. 교재에서는 ‘알고리즘과 함께 사용됩니다’로 되어 있습니다. 원형큐의 경우도 있어서, 순서 리스트라는 표현보다는 자료구조라는 표현이 더욱 정확하지 않을까 싶습니다.
  • 큐에서는 원소의 삭제 연산이 이루어지는 곳을 앞(front)이라 하고 삽입 연산이 이루어지는 끝을 뒤(rear)라고 합니다.
  • 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueue는 큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.
  • Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
  • Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull’ 메시지를 출력합니다.
  • Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
  • Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty’를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
  • 큐의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
  • 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자’를 사용합니다.

연결 리스트

  • 리스트의 ‘순서’는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’를 의미합니다.
  • 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있습니다. 자료의 삽입과 삭제가 빈번히 발생하는 상황에서, 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발합니다.
  • 포인터를 이용하는 방법은 원소의 자리에는 원소값을 저장하고, 다음 원소를 가리키는 정보의 자리에는 다음 원소가 저장될 위치의 주소값을 저장합니다. 조금 더 ‘프로그램’스럽게 설명하자면, 리스트의 원소 자리와 다음 원소를 가리키는 정보의 자리를 합쳐서 노드(node)라고 합시다. 노드에는 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가진다고 생각하면 됩니다. 이 포인터는 링크(link)라고도 부릅니다.
  • 포인터의 ‘메모리 주소값’이라는 것은 메모리에 저장되는 값의 위치라고 생각하면 됩니다. 메모리에 저장되는 값(데이터)은 저장 위치에 대한 주소를 가지며, 이 저장 위치를 이용해서 리스트의 원소값을 찾아갈 수 있습니다.
  • 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법이 구조체(struct)입니다.

연결 리스트 응용

  • 단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조이며, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 단점을 가집니다.
  • 이중 연결 리스트는 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 가집니다.
  • 단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 제안된 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있습니다.
반응형
저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

방송통신대학교 자료구조 기말 시험 대비 예상 문제 - 적합한 코드 찾기 유형  (0) 2023.12.02
자료구조 슈도 코드 및 개념 요약 정리 : 트리, 이진 트리 (바이너리 서치 트리), 스레드 트리, AVL/2-3트리, B 트리, 그래프, 프림/크루스칼/솔린 알고리즘  (2) 2023.12.02
자료구조 문제 풀이  (0) 2023.11.26
멀티웨이 탐색 트리 2 : 2-3 트리, 2-3-4 트리, 레드 블랙 트리  (1) 2023.11.26
멀티웨이 탐색 트리 1 - m원 탐색 트리, B 트리, B*트리, B+ 트리  (2) 2023.11.26

관련글

티스토리툴바