[C언어] Array & Linked lists (배열 & 연결 리스트)

배열 (Array)

 동일한 데이터 타입의 변수 여러 개를 하나로 묶어서 관리하기 위한 것이다.

배열요소가 메모리 내에 서로 붙어 있기 때문에 인덱스를 사용하여 필요한 요소가 있는 곳으로 단번에 찾을 수 있다(직접 접근)

int Number[2][3] = {{11, 22, 33}, {44, 55, 66}};

 C언어에서는 행 우선 순위로 사용되는데, 첫 행의 요소를 모두 나열한 다음에 둘째 행을 모두 나열하는 것으로 여전히 1차원으로 진행된다.

&Number[i - 1] = A + (i - 1) x sizeof(Element Type);

배열 Number의 첫 요소가 시작되는 주소는 &Number[0]으로 Number = &Number[0]; 임을 의미한다.

배열의 크기는 선언 시에 고정된다.

char Name[10] = "Jaewpark";

혹시나 이름이 길어서 허용된 공간 밖으로 Name[10]을 접근할 때에는 인덱스 범위 초과 오류에 직면하게 된다.

그렇다고 무조건 크게 선언을 하게 되면 메모리 공간이 낭비가 된다.

 

배열의 내용을 어셈블리어로 보게 되면,

1. 연속된 4바이트 공간 세 개를 확보하라.

2. 각각의 공간에 20, 50, 80 값을 넣어라.

3. 정수 포인터 A를 만들어라.

4. 포인터 A의 값을 배열 첫 요소의 시작 주소 값으로 초기하 하라.

어셈블리어 : 기계어와 일대일 대응이 되는 컴퓨터 프로그래밍의 저급 언어

 

포인터 산술연산

int Butter[1024];
for (int *p = Butter; p < &Butter[1024]; p++)
	*p = 5;

배열 인덱스

int Butter[1024];
for (int i = 0; i < 1024; i++)
	Butter[i] = 5;

 포인터 산술연산과 배열 인덱스의 결과는 같다.

 

아래와 같은 문법은 오류가 난다. 지역 변수인 정적 배열 Array를 선언하는 데 있어서 배열 크기는 컴파일 시에 고정되어야 한다. 즉, 실행시간에 넘겨질 파라미터 Size값으로 배열의 크기를 잡을 수는 없기 때문이다.

void Fuction(int Size)
{
	int Array[Size];
    ...
}

C++에서는 new를 이용하여 크기를 동적으로 지정할 수 있다.

 

---

리스트(List)

 

리스트에서 필요한 작업들을 하면 삽입, 삭제, 검색은 필수요소임을 알 수 있다.

또한, 구현을 하는데 있어서 구조체를 우선적으로 선언되어야 한다.

 

우선 배열로 리스트를 구현을 하게 되면, 직접 접근이 가능하는데, 인덱스가 인접해있기에 빠른 속도로 검색이 가능하다. 그러나 단점으로 데이터 최대 개수를 컴파일 이전에 미리 선언을 해야하고 이동에 따른 시간적 부담(아이템 10만 개에서 첫번째에 삽입을 하게되면 10만 개 모두 이동) 크다.

 

연결 리스트(Linked List)

연결리스트에서는 배열과 다르게 포인터로 찾아낸다. 그렇기에 구조체 선언 시, 데이터 그리고 포인터를 담을 포인터 노드가 필요한다. 포인터가 가르키는 것은 노드 전체이다. 또한 처음을 가르키는 head로부터 연결되어서 나가는 방식이다.

 

구현해야 하는 연산들

1. 삽입 : 항목을 리스트에 추가

2. 삭제 : 지정된 위치의 항목을 삭제

3. 리스트 삭제 : 리스트의 모든 항목을 삭제

 

삽입 관련 되어서 배열과 연결리스트 차이

1. 연결리스트에서는 배열처럼 공간이 꽉 찬 상태인지 테스트할 필요가 없다.

2. 데이터가 중간에 삽입 일어나도 나머지 데이터가 이동할 필요가 없다.

3. 삽입 직접 노드를 찾는 작업이 배열에 비해 오래 걸린다. 배열은 i번째 직접접근이 가능한 데 반해서 포인터를 따라 가야하기 때문이다.

 

연결리스트 중에서도 이중 연결과 원형 연결이 존재한다.

1. 이중 연결 리스트 : next 만 가르키는 것 말고도 prev로 이전 노드도 가르키게 하는 구조로 이전 노드로 돌아가는 작업이 수월하게 되며, 오름차순으로 정렬이 되어있는 부분을 내림차순으로 역으로 볼 수도 있는 정보를 더 빠르게 확인할 수 있다.

2. 원형 연결 리스트 : 사용자가 번갈아 가면서 작업을 하고 순서대로 무언가를 하는 과정하는 곳에 쓰기 좋은 것으로 리스트가 어느 부분에서 끝나는 것이 아닌 원같이 연결이 되어있는 형태이다.

3. 원형 이중 연결 리스트 : 1번과 2번의 장점을 살린 연결 리스트이다.

 

메모리 낭비를 덜 하기 위해서 사용

---

• 배열 리스트 코드 구현

#ifndef _ARRAYLIST_
#define _ARRAYLIST_

#define MAX_LIST_SIZE 100

typedef int element;

typedef struct {
    element array[MAX_LIST_SIZE];
    int size;
} ArrayList;

void error(char *message);
void init(ArrayList *List);
int is_empty(ArrayList *List);
int is_full(ArrayList *List);
element get_entry(ArrayList *List, int pos);
void print_list(ArrayList *List);
void insert_last(ArrayList *List, element item);
void insert(ArrayList *List, int pos, element item);
element delete(ArrayList *List, int pos);

#endif

#include "arraylist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void error(char *message){
    fprintf(stderr, "%s/n", message);
    exit(1);
}

void init(ArrayList *List){
    List->size = 0;
}

int is_empty(ArrayList *List) {
    return (List->size == 0);
}

int is_full(ArrayList *List) {
    return (List->size == MAX_LIST_SIZE);
}

// 특정 위치의 항목 반환
element get_entry(ArrayList *List, int pos) {
    if (pos < 0 || pos > List->size)
        error("위치 오류");
    return (List->array[pos]);
}

void print_list(ArrayList *List) {
    int i;
    for (i = 0; i < List->size; ++i)
        printf("%d->", List->array[i]);
    printf("\n");
}

//끝에 삽입
void insert_last(ArrayList *List, element item) {
    if (is_full(List))
        error("리스트 오버플로우");
    List->array[List->size++] = item;
}

void insert(ArrayList *List, int pos, element item) {
    if (!is_full(List) && (pos > 0) && (pos < List->size)) {
        for(int i = (List->size - 1); i < pos; ++i)
            List->array[i + 1] = List->array[i];
        List->array[pos] = item;
        List->size++;
    }
}

// 특정 위치 삭제
element delete(ArrayList *List, int pos) {
    element item;

    if (pos < 0 || pos > List->size)
        error("위치 오류");
    item = List->array[pos];
    for(int i = pos; i < (List->size - 1); ++i)
        List->array[i] = List->array[i + 1];
    List->size--;
    return item;
}

 

아래는 Data Structures and Algorithms Made Easy 를 참고 하였습니다.

• 단일 연결 리스트 : 마지막 노드는 NULL을 가리켜 마지막임을 표시

struct ListNode {
	int data;
    struct ListNode *next;
}

 

• 리스트 탐색 

int ListLength(struct ListNode *head) {
	struct ListNode *current = head;
    int count = 0;
    while (current != NULL) {
    	count++;
        current = current->next;
    }
    return (count);
}

 

• 리스트 삽입

void InsertInLinkedList(struct ListNode **head, int data, int position) {
	int k = 1;
    struct ListNode *p , *q, *newNode;
    newNode = (ListNode *)malloc(sizeof(struct ListNode));
    if (!newNode) {
    	printf("Memory Error");
        return ;
    }
    newNode->data = data;
    p = *head;
  	if (position == 1) {
    	newNode->next = p;
        *head = newNode;
    }
    else {
    	while ((p != NULL) && (k < position - 1)) {
        	k++;
            q = p;
            p = p->next;
        }
        if (p == NULL) {
        	q->next = newNode;
            newNode->next = NULL;
        }
        else {
        	q->next = newNode;
            newNode->next = p;
        }
    }
}

 

• 리스트 삭제 (중간 노드)

void DeleteNodeFromLinkedList(struct ListNode **head, int position) {
	int k = 1;
    struct ListNode *p, *q;
    if (*head == NULL) {
    	printf("List Empty");
        return ;
    }
    p = *head;
    if (*position == 1) {
    	p = *head;
        *head = *head->next;
        free (p);
        return ;
    }
    else {
		while ((p != NULL) && (k < position - 1)) {
        	k++;
            q = p;
            p = p->next;
        }
        if (p == NULL) {
        	printf("Position does not exitst");
        else {
        	q->next = p->next;
            free (p);
        }
    }
}

• 리스트 삭제 (단일 연결)

void DeleteLinkedList(struct ListNode **head) {
	struct ListNode *auxilaryNode, *iterator;
    iterator = *head;
    while (iterator) {
    	auxilaryNode = iterator->next;
        free(iterator);
        iterator = axilaryNode;
    }
    *head = NULL;
}

---

이중 연결 리스트

: 구조는 위와 동일하지만 이중으로 연결하여 양방향으로 탐색, 저장공간과 연산이 조금 더 많아지는 단점이 있다.

struct DLLNode {
	int data;
    struct DLLNode *next;
    struct DLLNode *prev;
}

원형 연결 리스트

: 위와 같은 연결 리스트는 NULL로 마지막을 인식하지만, 원형은 head 노드를 사용하여 NULL 이라는 끝을 인식한다.