Variation of linked lists

학부 수업 정리/자료구조

Variation of linked lists

supersumin 2025. 3. 23. 01:43

Signly linked lists

Background

Typedef

typedef는 C/C++에서 사용자가 정의한 자료형에 새로운 이름을 부여하여 복잡한 자료형 이름을 선언할 때 간단하게 만드는 데 사용된다.

struct Person {
    char name[50];
    int age;
};

struct Person p1;

struct를 직접 사용할 때는 struct Person이라고 매변 명시한 뒤 변수명 p1을 선언해야 한다.

typedef struct {
    char name[50];
    int age;
} Person;

Person p1;

typedef를 통해 사용자 지정 struct 변수를 선언할 때 struct 키워드 없이 간단하게 사용할 수 있다.

Dynamic memory allocation

RAM에서 관리하는 memory 공간 중 동적 메모리가 할당되는 공간인 Heap segment에서 memory를 할당받아 pointer에 저장한다.

할당받은 memory는 연속된 byte 블록으로 잡히며 이 memory의 첫 번째 주소가 pointer에 저장된다.

memory를 할당하는 함수로는 malloc(), calloc() 등이 있으며, 이 함수들은 void* 타입의 포인터를 반환한다. 따라서 사용자가 어떤 데이터 타입을 가리키는 포인터 변수를 선언하는지에 따라 casting해줘야 한다.

Struct를 static memory allocation하기 보다 dynamic memory allocation이 memory에서 효율적

struct(구조체) 또한 int와 같이 자료형으로서 정적할당보다 동적할당이 memory 관리 측면에서 효율적이다. 프로그램 실행 중에 필요한 만큼 memory를 확보하고 사용 후 명시적으로 해제할 수 있기 때문이다.

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

typedef struct node {	// typedef로 인해 변수 선언이 struct를 명시해주지 않아도 된다.
	int data;
	struct node* next;
} Node;

//struct node {
//	int data;
//	struct node* next;
//};
//typedef struct node Node;	// typedef를 이후에 선언할 수도 있다.

int main()
{
	Node nodes[4];	// 정적 할당된 struct node 배열

	nodes[0].data = 1;	// node의 member에 접근할 때 dot operator를 사용한다.
	nodes[0].next = &nodes[1];	// 첫 번째 요소의 다음 주소를 두 번째 index로 초기화한다.

	nodes[1].data = 2;
	nodes[1].next = &nodes[2];

	nodes[2].data = 3;
	nodes[2].next = &nodes[3];

	nodes[3].data = 4;
	nodes[3].next = NULL;

	// print the linked list
	Node* current = &nodes[0];	// node array에 첫 번째 주소를 current에 받아 각 node를 출력한다.
	while (current != NULL) {
		printf("%d\n", current->data);
		current = current->next;
	}

	/////////////////////////////////////
	//// dynamic memory allocation - pointer & arrow operation, 각 node를 동적할당하여 사용한다.
	//Node* a = (Node*)malloc(sizeof(Node));	// 하나의 node에 대해 각각 동적할당 해준다.
	//Node* b = (Node*)malloc(sizeof(Node));	// 동적할당 해주기 때문에 node에 접근할 때는 pointer로 접근한다.
	//Node* c = (Node*)malloc(sizeof(Node));
	//
	//a->data = 1;	// 접근하려는 struct 변수가 pointer일 때, -> operator를 사용한다.
	//a->next = b;
	//
	//b->data = 2;
	//b->next = c;
	//
	//c->data = 3;
	//c->next = NULL;
	//
	//free(a);
	//free(b);
	//free(c);
	//////////////////////////////

	return 0;
}

Call by value and reference

Singly linked list에서 함수에 head를 인자로 넘길 때 head 포인터 자체를 바꾸는 insert나 delete 와 같은 연산을 하기 위해서는 node*가 아니라 node** 타입으로 넘겨야 한다.

Head가 선언될 때 node* 타입으로 선언되는데 이 자료형으로 그대로 함수에 넘기게 되면 포인터의 값을 복사해서 함수에 전달하게 되고, 이는 함수 내에서 head를 변경하더라고 원래 리스트의 head에는 반영되지 않기 때문이다.

List operations

Head란?

Head는 list의 첫 번째 node를 가리키는 포인터로 리스트의 시작 주소를 의미한다. 이는 array이 첫 번째 요소의 주소를 기준으로 연산되는 것과 유사하다.

List가 비어있는 경우 head는 NULL을 가리킨다.

Node 생성

Node 구조체를 만들기 위해서 sizeof(Node)만큼 메모리를 동적으로 할당받고 그 주소를 Node* 타입 포인터로 받는다.
메모리 할당은 malloc 함수를 통해 이루어지며, 할당에 실패할 경우 NULL을 반환한다.
생성에 성공하면 해당 노드의 data에 값을 저장하고, next 포인터는 NULL로 초기화하여 아직 연결된 노드가 없음을 나타낸다.

// Function to create a new Node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));  // 동적 메모리 할당
    
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    
    newNode->data = data;      // 값 설정
    newNode->next = NULL;      // 다음 노드는 아직 없으므로 NULL
    return newNode;            // 새로 생성된 노드 반환
}

리스트 맨 앞(head)에 새 노드를 삽입

새로운 노드를 삽입하기 위해 먼저 createNode() 함수를 통해 노드를 생성해야 한다.
리스트가 비어있다면(head == NULL) 새 노드를 그대로 head로 초기화 하고, 리스트가 비어있지 않다면 새 노드의 next를 기존 head를 가리키게 한 뒤, 새 노드를 head로 초기화한다.

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    
    if (!newNode) return;	# Node가 비어있으면 NULL이고 함수가 종료된다.
    
    newNode->next = *head;	# head가 node** 타입 포인터이므로 *연산을 통해 head의 주소에 접근한다.
    *head = newNode;
}

리스트 맨 뒤(tail)에 새 노드를 삽입

노드를 생성하고 실패 시 함수를 종료하는 return
temp 포인터를 이용해 리스트의 맨 끝으로 이동, 이 때 while 문 사용
마지막 노드의 next에 새 노드 연결, temp->next에 newNode 삽입하기

// Function to insert a new Node at the tail
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (!newNode) return;  // 노드 생성 실패 시 종료

    // 리스트가 비어 있으면 새 노드를 head로 지정
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // temp를 이용해 리스트 끝까지 이동
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // 마지막 노드의 next에 새 노드 연결
    temp->next = newNode;
}

지정된 위치에 새 노드를 삽입

노드를 삽입할 것 createNode()를 호출해 새 노드를 동적 할당해야 한다.
삽입 위치가 head일 경우 *head를 업데이트 해야 한다.
지정된 위치까지 가는데 position과 currentIndex를 사용하고, 새 노드를 연결할 때는 꼭 새 노드를 먼저 기존 노드에 연결해줘야 한다.

void insertAtPosition(Node** head, int position, int data) {
    if (position < 0) {
        printf("Invalid position!\n");
        return;
    }

    Node* newNode = createNode(data);
    if (!newNode) return;

    // If inserting at the head (position 0)
    if (position == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    // Traverse to the node just before the desired position
    Node* temp = *head;
    int currentIndex = 0;
    while (temp != NULL && currentIndex < position - 1) {
        temp = temp->next;
        currentIndex++;
    }

    // If position is out of range
    if (temp == NULL) {
        printf("Position out of range!\n");
        free(newNode);
        return;
    }

    // Insert the new Node
    newNode->next = temp->next;
    temp->next = newNode;
}

노드 삭제

현재 노드(temp)와 그 이전 노드(prev)를 연결해줘야 한다. 단방향 연결이기 때문에 이전 노드를 추적하기 위해 prev 포인터를 따로 사용해야 한다.
또한, 삭제할 노드가 head일 수도 있기 때문에, 이 경우는 별도로 처리해주어야 한다.

void deleteNode(Node** head, int key) {
    Node* temp = *head, * prev = NULL;

    // Case 1: head 노드가 삭제 대상일 경우
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        printf("Node with value %d deleted.\n", key);
        return;
    }

    // Case 2: 삭제할 노드를 찾을 때까지 탐색
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 삭제할 노드가 없는 경우
    if (temp == NULL) {
        printf("Node with value %d not found.\n", key);
        return;
    }

    // 이전 노드(prev)가 현재 노드(temp)의 다음 노드를 가리키도록 연결
    prev->next = temp->next;
    free(temp);
    printf("Node with value %d deleted.\n", key);
}

탐색

찾고자 하는 값을 리스트의 앞(head)부터 끝까지 순차적으로 비교한다.
찾으면 true를 반환하고, 끝까지 없으면 false를 반환한다.

bool searchNode(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return true;
        }
        temp = temp->next;
    }
    return false;
}

해제 하기

리스트 전체를 해제하려면 끝까지 순회해야 하므로 temp가 NULL이 될 때까지 반복
현재 노드를 삭제하기 전에 다음 노드를 가리키는 next 포인터를 저장해둬야 한다.

void freeList(Node** head) {
    Node* temp = *head;
    while (temp != NULL) {
        Node* next = temp->next; // 다음 노드를 미리 저장
        free(temp);              // 현재 노드 메모리 해제
        temp = next;             // 다음 노드로 이동
    }
    *head = NULL; // head 포인터도 NULL로 초기화
}

출력

리스트의 끝까지 출력이 진끝까지 출력하므로 temp가 NULL일 때까지 반복
각 반복에서 temp는 temp->next로 업데이트되며, 노드의 data 값을 출력

// Function to print the linked list
void printList(Node* head) {
    Node* temp = head;
    if (!temp) {
        printf("List is empty.\n");
        return;
    }
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;  // 다음 노드로 이동
    }
    printf("NULL\n");
}

Circular linked lists

Circular linked list는 마지막 노드가 다시 첫 번째 노드를 가리켜 원형 구조를 이루는 연결 리스트이다. 이 구조에서 head 포인터가 어디를 가리키는지에 따라 연산의 시간 복잡도가 달라진다.

Head가 첫 번째 노드를 가리키는 경우

Insert

맨 앞에 삽입: 마지막 노드가 새 노드를 가리키기 위해 마지막 노드를 찾기 위해 전체를 순회 하므로 O(N)
맨 뒤에 삽입: 마지막 노드를 생성하기 위해 마지막 노드를 찾기 위해 순회하므로 O(N)

Delete

첫 번째 노드 삭제: head를 한 칸 옆으로 옮기고 마지막 노드는 다시 head를 가리켜야 하기 때문에 연산량은 O(N)
마지막 노드 삭제: 마지막 노드를 찾아서 삭제해야 하므로 O(N)

Head가 마지막 노드를 가리키는 경우

Insert

맨 앞에 삽입: newNode->next = *head->next, *head->next = newNode 만 하면 되므로 O(1)
맨 뒤에 삽입: newNode->next = head->next, head->next = newNode, head = newNode 하면 되므로 O(1)

Delete

첫 번째 노드 삭제: head->next = head->next->next 로 연결만 바꾸면 되므로 O(1)
마지막 노드 삭제: 마지막 노드를 새로 업데이터 해야하므로 O(N)

	Insertion		Deletion
	At the front	At the end	At the front	At the end
Head = 첫 번째 노드	O(N)	O(N)	O(N)	O(N)
Head = 마지막 노드	O(1)	O(1)	O(1)	O(N)

Doubly linked lists

앞뒤로 이동 가능한 연결 리스트이다. 단일 연결 리스트보다 메모리는 더 쓰이지만, 양방향 탐색 및 삽입/삭제 연산에서 유리하다.

각 노드는 prev, next 포인터를 가진다.

Deletion

삭제할 노드의 이전 노드와 다음 노드를 연결해주면 된다.

target->prev(A)->next = target(B)->next;
target->next(C)->prev = target(B)->prev;
free(target);

Insertion

먼저 newNode의 포인터들을 세팅한 후, 기존 노드들의 포인터를 업데이트 해줘야 한다.

newNode->prev = current;
newNode->next = current->next;
current->next->prev = newNode;
current->next = newNode;

'학부 수업 정리 > 자료구조' 카테고리의 다른 글

Queue (0)	2025.04.04
Stack (0)	2025.03.31
Complexity (0)	2025.03.22
Linked lists (0)	2025.03.18
Constant (상수) (0)	2025.03.13

현재글Variation of linked lists

supersumin 님의 tistory

머리속 정리하 우와악

Today :
Yesterday :

일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

supersumin 님의 tistory