[자료구조] C/C++ 단일 링크드리스트

친구를 통해 링크드리스트에 대한 이론과 한번쯤은 직접 만들어보라고 조언해 준적이 있다.

우선 링크드리스트가 무엇인지는 위키백과를 참고하였다. 

링크 : https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

이곳에서 단일 링크드 리스트에 대해 살펴보자.

정리하면, 각 노드가 데이터(값)와 다음노드나 이전노드를 연결하는 포인터를 가지고 있는 자료구조이다.

특징은 자료의 추가와 삭제가 O(1)이며 동적할당을 통해 연속적인 기억장소 할당이 필요하지 않지만 특정데이터를 검색하는데 O(n)의 시간이 걸린며 포인터의 사용으로 저장공간의 낭비가 있다.

C / C++의 단일 링크드리스트의 코드를 보며 살펴보자.

자세한 내용은 아래 출처에서 확인할 수 있다.

출처 : https://www.crocus.co.kr/334?category=150836

C언어

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<malloc.h>
 
using namespace std;
 
 
// C언어 단일 연결리스트
typedef struct List {
    struct List *next; // 연결도구
    int data; // 데이터
}in;
// 단일 연결리스트의 기본구조모양
 
int main() {
    List* node = (List*)malloc(sizeof(List)); // 첫 노드생성
    node->data = 3;
    node->next = NULL; // 가리키는게 없음
 
    List* node2 = (List*)malloc(sizeof(List)); // 다른 노드생성
    node2->data = 100; // 다른노드에 값 넣음
    node2->next = node->next; // 다음노드가 가리키는것은 첫 노드가 가리키는 포인터 넣음 -> NULL을 가리킴
    node->next = node2; // node->next가 가리키는 NULL을 node2로 변경 -> 첫 노드가 node2를 가리킴
 
    List node3;               //동적할당이 아닌 구조체타입으로도 생성가능
    node3.data = 200;
    node3.next = node2->next;
    node2->next = &node3;     //node2->next 는 포인터이기때문에 &연산자사용
 
    printf("node -> next   :%8d       node -> data    :%8d  \n", node->next, node->data);
    printf("node2 -> next  :%8d       node2 -> data   :%8d   \n", node2->next, node2->data);
    printf("node3 -> next  :%8d       node3 -> data   :%8d  \n", node3.next, node3.data);
}

C++ 클래스

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<malloc.h>
 
using namespace std;
 
 
//C++ 단일 연결리스트
 
class list {
private:
    list *Next; // 연결 도구
    int val; // 데이터 
public:
    list(int a) : Next(NULL), val(a) {}; //생성자 선언 및 바로 초기화
    ~list() {}; //소멸자
    int value() const { return val; } 
    list *get() const { return Next; }   //노드의 값 불러오기용
    void setNext(list *el) { Next = el; }  //노드 추가
    //void Delete(list *a, list *b) {}
};
// 기본 수도코드 
 
// 실제 적용
class node {
private:
    int data;
    node *next;
public:
    node(int val) : next(NULL), data(val) {};
    int getvalue() const { return data; }
    node *get() const { return next; }
    void setnext(node *Nnode) { next = Nnode; }
};
int main()
{
    //클래스를 이용한 연결리스트
    node *head = NULL, *tail = NULL, *cur = NULL, *Nnode = NULL;
    // 얘들은 포인터 공간을 할당 받지 않은 포인터
    int val;
    
    while (1) {
        cin >> val;
        if (val == 0) {// 0이 입력들어온다면 프로그램을 종료
            break;
        }
        //추가
        Nnode = new node(val); // Nnode에 공간을 할당하고 생성자 호출, 생성자는 입력값과 초기 next포인터를 NULL로 초기화
        if (head == NULL) head = Nnode; // 시작 : head는 Nnode가리킴
        else tail->setnext(Nnode);  // tail의 next는 새로 생성된 Nnode의 next 즉, NULL을 가리킴 
        tail = Nnode; // tail포인터는 Nnode의 추가된 값과 NULL을 가리키게 됨.
        cout << head->get() << "   " << head->getvalue() << "   " << tail->get() << "    " << tail->getvalue() << endl;
    }
    return 0;
}