[데이터 구조] 배열(Array)와 연결리스트(Linked List)로 리스트 추상자료형 구현 (with C)

배열(Array)

• 순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들
• 배열명, V: 배열 전체를 일컫는 기호
• 배열 크기, N: 원소를 저장하는 셀들의 개수
• 배열 첨자, i: 셀의 순위 = 상대적 위치

 

배열의 메모리 할당

• 컴파일 시 배열의 셀들은 베이스(base)라고 불리는 배열의 첫째 셀 위치부터 시작해 차례로 할당됨
• 각 셀은 베이스로부터 오프셋(offset)만큼 떨어짐
• 행 우선 순서 = 저차원 우선 순서

 

2차원 배열

• 테이블이라고도 불림
• 1차원과 2차원은 각각 행, 열로도 불림

---

연결리스트(linked list)

• 동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들
• 연결리스트 명: L, 연결리스트의 시작 위치, 첫 노드의 주소
• 연결리스트 크기: n, 연결리스트 내 노드의 수
• 종류 - 단일, 이중, 원형, 헤더 및 트레일러, 복합 연결리스트
• List, Stack, Queue(고급 데이터 구조들)를 연결리스트(재료)로 구현할 수 있다.

 

노드에 의한 메모리 할당

• 노드: 한 개의 데이터 원소를 저장하기 위해 동적 메모리에 할당된 메모리
• 노드를 위한 메모리의 동적 할당(allocation)과 해제(deallocation)는 실행 시간에 system call에 의해 처리
  • getnode(): 노드를 할당 후 그 노드의 주소 반환 (동적 메모리가 고갈된 시점이면 null 포인터 반환)
  • putnode(i): 주소 i의 노드에 할당되었던 메모리의 사용을 해제 후 이를 동적 메모리에 반환 (메모리 재활용 위해)

 

단일연결리스트

• 연속 노드로 구성된 가장 단순한 연결 데이터 구조
• 노드 저장 내용
  • 원소(element): 데이터 원소, data field
  • 링크(link): 다음 노드의 주소, 다음 노드의 주소가 없는 경우 null 링크 저장, link field
• 접근점
  • 첫 노드 = 헤드 노드의 주소
• 단방향의 아쉬움 → → 이중 연결리스트 등장

 

이중연결리스트

• 추가 링크 사용해 역방향 순회 가능  
• 노드 저장 내용
  • 원소
  • 링크: 다음 노드의 주소
  • 링크: 이전 노드의 주소
• 접근점
  • 헤드노드의 주소
  • 테일노드의 주소

 

 

원형연결리스트

• 마지막 노드의 링크 = 헤드노드의 주소
• 접근점: 헤드노드의 주소

 

헤더와 트레일러

• 헤드노드 바로 앞에 특별한 헤더(header) 노드 추가해 작업 편의성 증진
• 같은 목적으로 테일노드 바로 뒤에 특별한 트레일러 (trailer) 노드 추가 가능
• 특별 노드 저장내용
  • 모조 원소(=데이터는 따로 저장하지 않은 특별한 노드, dummy element)
• 접근점
  • 헤더노드 또는 트레일러노드의 주소

---

리스트 ADT (Abstract Data Type, 추상자료형)

• 연결 리스트와 다름. 연결 리스트는 리스트나 다른 ADT 구현하기 위한 도구
• 원소에 대한 접근 도구
  • 순위(rank)
• 메쏘드
  • 일반 메쏘드
    • boolean isEmpty(): 비어 있는지 안 비어 있는지 반환
    • integer size(): 리스트의 크기 반환
    • iterator elements()
  • 접근 메쏘드
    • element get(r): 리스트에서 r의 상대적 위치
  • 갱신 메쏘드
    • element set(r, e)
    • add(r, e), addFirst(e), addLast(e): 원소 삽입 (특정한 위치에 원소 삽입 포함)
    • element remove(r), element removeFirst(), element removeLast(): 원소 제거 (특정한 위치의 원소 삭제 포함)

---

단순연결리스트로 리스트 ADT 구현 (with C)

// 단순연결리스트로 리스트 ADT 구현

#include <stdio.h>
#include <stdlib.h>

// 구조체 선언 (새 노드)
typedef struct ListNode 
{
    int data; //data field
    struct ListNode* link; // 자기참조 구조체
}ListNode;

typedef struct
{
    ListNode* head; // head 포인터 구조체
}LinkedListType;

void init(LinkedListType* L)
{
    L->head = NULL; // head는 NULL로 초기화
}

void addFirst(LinkedListType* L, int item)
{
    ListNode* node = malloc(sizeof(ListNode)); 
    // getnode 역할, malloc으로 직접 노드 생성
    // malloc 함수는 주소를 리턴하니까 포인터로 받기
    // malloc 함수는 어떤 대상을 위한 공간 만들어질지 몰라 항상 void형 주소 리턴 
    node->data = item; // node의 data 필드에 item 집어넣기
    node->link = L->head; // 내가 먼저 들어가는 것, 현재 헤드가 내 뒤로 들어와야함 --> 현재 head가 node link로
    L->head = node; // 내가 현재 head
}   

void addLast(LinkedListType* L, int item)
{
    ListNode* node = malloc(sizeof(ListNode));
    ListNode* before = L->head;  
    while(before->link != NULL)
        before = before->link; // 오른쪽으로 이동
    node->data = item;
    node->link = NULL;
    before->link = node;
}

void add(LinkedListType* L, int pos, int item)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    ListNode* before = L->head;
    for(int i = 0; i < pos - 1; i++)
        before = before->link; // before -> link는 before 오른쪽 노드니까 오른쪽으로 한칸씩 이동
    node->data = item;
    node->link = before->link;
    before->link = node;
}

// remove
void remove1(LinkedListType* L, int pos)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    ListNode* before = L->head;
    for(int i = 0; i < pos - 1; i++)
        before = before->link;
    before->link = before->link->link; // 없앨 노드 연결 끊기
}


void removeFirst(LinkedListType* L)
{
    L->head = L->head->link;
}

void removeLast(LinkedListType* L)
{
    ListNode* before = L->head;
    for(int i = 0; i < sizeof(L); i++)
        before = before->link;
    before->link = NULL;    
}

// position에 있는 값 가져오는 함수
int get(LinkedListType* L, int pos)
{
    ListNode* p = L->head;
    for(int i = 1; i < pos; i++)
        p = p->link;
    return p->data;
}


void set(LinkedListType* L, int pos, int item)
{
    ListNode* p = L->head;
    for(int i = 1; i < pos; i++)
        p = p->link;
    p->data = item;
}

void printList(LinkedListType* L)
{
    for(ListNode* p = L->head; p != NULL; p = p->link)
        printf("[%d] -> ", p->data);
    printf("NULL\n");
}

// addLast 구현, add랑 비슷한데 for문에서 좀 생각해야 함
// 현재 연결리스트에서 제일 마지막 노드까지 가고 그 노드가 before 노드가 되어 내가 걔랑 연결되어지고 등등..
// remove, removeFirst, removeLast

void main()
{
    LinkedListType list;
    init(&list);
    
    addFirst(&list, 10); printList(&list);
    addFirst(&list, 20); printList(&list);
    addFirst(&list, 30); printList(&list);
    getchar(); // 잠깐 멈춤
    add(&list, 1, 40); printList(&list);
    add(&list, 1, 50); printList(&list);
    add(&list, 3, 60); printList(&list);
    
    addLast(&list, 70); printList(&list);

    removeFirst(&list); printList(&list);
    removeLast(&list); printList(&list);
    remove1(&list, 3); printList(&list);

    int pos;
    printf("\n 몇 번 노드의 값을 반환할까요? ");
    scanf("%d", &pos);
    printf("%d번 노드의 값은 %d\n", pos, get(&list, pos));
}

---

배열로 리스트 ADT 구현 (with C)

// 배열로 리스트 ADT 구현

#include <stdio.h>
#include <stdlib.h>

#define SIZE 100

typedef struct // array로 선언
{
    int V[SIZE]; // list 역할을 할 배열 
    int n; // 전체 list 요소 개수 기억하는 변수
}ArrayList; // 이 구조체의 이름을 ArrayList로 선언

void init(ArrayList* L) // 주소 오니까 포인터 L로 받기
{
    L->n = 0; // L 원소의 개수 0개
}

// traverse method (접근 method)
void traverse(ArrayList* L)
{
    for(int i = 0; i < L->n; i++) // 원소의 개수는 마지막 element 바로 다음 첫 번째 비어있는 칸 가리킴
        printf("[%d] ", L->V[i]); // data field값
    printf("\n");
}

void add(ArrayList* L, int pos, int item) // pos: rank 역할, item: 삽입될 값
{
    if(L->n == SIZE)
    {
        printf("fullListException...\n");
        exit(1); // 예외처리 후 프로그램 끝내기
    }
    // invalidPosException... 0 <= post <= L->n
    for(int i = L->n - 1; i >= pos; i--)
        L->V[i+1] = L->V[i]; // 한 칸씩 오른쪽으로 위치 이동
    L->V[pos] = item;
    L->n++;
}

int remove1(ArrayList* L, int pos)
{
    // exception 처리
    int item = L->V[pos]; // 나중에 이 값 return
    for(int i = pos + 1; i <= L->n - 1; i++)
        L->V[i - 1] = L->V[i];
    L->n--;
    return item;
}

void main()
{
    ArrayList list; // main에서 ArrayList 선언
    
    init(&list); // 구조체 포인터로 전달하며 초기화 --> 변경되는 내용을 공유할 수 있게
    
    add(&list, 0, 10); traverse(&list);
    add(&list, 0, 20); traverse(&list);
    add(&list, 1, 30); traverse(&list);
    add(&list, 1, 40); traverse(&list);
    add(&list, 3, 50); traverse(&list);
    
    getchar();
    remove1(&list, 1); traverse(&list);
    remove1(&list, 2); traverse(&list);
}