단일 연결 리스트 Singly Linked List

배열: 여러가지 값들을 저장하고 처리하는 방법 중 하나

배열의 경우 중간의 원소를 삭제하거나, 중간에 값을 삽입할때는 굉장히 비효율적.

이러한 단점을 보완하기 위해 사용하는것이 바로 연결 리스트.

 

연결리스트에 접근하기 위해 헤드 포인터 즉 첫 번째 노드를 가르키는 포인터 값만 알면 리스트 안의 모든 노드에 접근이 가능하다.

 

 

---

 

 

구조체를 선언하고 정수형 데이터를 저장할 수 있는 단일 연결 리스트를 구현해보자.

 

 

1. 구조체선언

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

 

data: 노드에 저장할 데이터
next: 다음 노드의 주소 저장할 포인터

 

2. 개별 노드 초기화

void initNode(Node*& head, int data) {
    head = new Node;
    head->data = data;
    head->next = nullptr;
}

new연산자를 이용해 새로운 노드를 동적할당해준다.

head가 가리키는 노드의 data에 data라는 값 넣어주기.

마지막 노드의 next는 nullptr로 설정해준다.

 

 

3. 연결된 모든 노드의 값을 순서대로 출력

void printList(Node* head) {
    Node* current = head;
    while(current != nullptr) { 
        cout << current->data << " ";
        current = current->next;
    }
cout << endl;
}

현재 노드가 nullptr가 아닐때까지 반복수행한다.

 

4. 마지막 노드의 뒤에 새로운 노드 추가

void appendNode(Node*& head, int data) {
// 새 노드 생성 및 값 할당
Node* newNode = new Node;
newNode->data = data; 
newNode->next = nullptr;

//리스트에 새 노드 추가
if (head == nullptr) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}

만약 리스트가 비어있다면 새 노드를 설정해주고,

아니라면 끝을 찾고 그 뒤에 새로운 노드를 연결해준다.

 

5. n번째 위치에 있는 노드 삭제

void deleteNode(Node*& head, int position) {
    
    if (head == nullptr) return;

    Node* temp = head;

    // 첫 번째 노드를 삭제하는 경우
    if (position == 0) {
        head = temp->next;
        delete temp;
        return;
    }

    // 그 외의 경우, n번째 위치로 이동
    for (int i = 0; temp != nullptr && i < position - 1; i++) {
        temp = temp->next;
    }

    // 유효성 검사: 위치가 리스트범위를 벗어나거나, 삭제할 노드가 없으면 종료
    if (temp == nullptr || temp->next == nullptr) return;

    Node* next = temp->next->next;
    delete temp->next;
    temp->next = next;
}

 

6. n번째 위치에 노드 추가

void insertNode(Node*& head, int position, int data) {
    Node* newNode = new Node;
    newNode->data = data;

    if (position == 0) {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;
    for (int i = 0; temp != nullptr && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == nullptr) return;

    newNode->next = temp->next;
    temp->next = newNode;
}

 

7. 임의의 값을 찾아 해당 값을 가진 노드의 주소 반환

Node* findNode(Node* head, int data) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == data) {
            return current;
        }
        current = current->next;  
    }
    return nullptr;
}

 

메인함수에서 실행해보자

int main() {
    Node* head = nullptr;

    // 개별 노드 초기화
    initNode(head, 10);
    appendNode(head, 20);
    appendNode(head, 30);
    
    // 모두 출력
    cout << "Initial List: ";
    printList(head);

    // 마지막 노드 뒤에 새로운 노드 추가
    appendNode(head, 6);
    cout << "After appending 6: ";
    printList(head);

    // n 번째 위치에 노드 추가
    insertNode(head, 1, 25);  // 1번째 위치에 25 삽입
    cout << "After inserting 25 at position 1: ";
    printList(head);

    // n 번째 위치에 있는 노드 삭제
    deleteNode(head, 3);  // 3번째 위치 노드 삭제
    cout << "After deleting node at position 3: ";
    printList(head);
    
    // 4-1. n 번째 위치에 있는 노드 삭제
    deleteNode(head, 2);  // 2번째 위치 노드 삭제
    cout << "After deleting node at position 2: ";
    printList(head);

    // 6. 임의의 값을 찾아 해당 값을 가진 노드의 주소 반환
    Node* foundNode = findNode(head, 6);
    if (foundNode != nullptr) {
        cout << "Node with data 6 found at address: " << foundNode << endl;
    } else {
        cout << "Node with data 6 not found" << endl;
    }

    return 0;
}