Linked List

가변배열과 다르게 연속적인 메모리를 갖지 않는다.

메모리에 데이터와 다음 데이터의 주소를 갖는다.

데이터의 단위는 노드이다.

 

장점: 원하는 위치에 바로 데이터 삽입이 가능하다. O(1)

단점: 인덱스가 없어 검색을 시작하면 맨 처음부터 순차적으로 진행한다. O(n)

 

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

// linkedList.h

#pragma once

typedef struct lNode
{
    int data;
    lNode *nextNode;
} LNode;

typedef struct linkedList
{
    int count;
    LNode *headNode; // 첫 번째 노드의 주소
} LinkedList;

void InitList(LinkedList *_pList);
void RPushList(LinkedList *_pList, int data);
void LPushList(LinkedList *_pList, int data);
void ReleaseList(LinkedList *_pList);

#include "linkedList.h"
#include <iostream>

void InitList(LinkedList *_pList)
{
    _pList->count = 0;
    _pList->headNode = nullptr;
};

void RPushList(LinkedList *_pList, int data)
{
    LNode *pNode = (LNode *)malloc(sizeof(lNode));
    pNode->data = data;
    pNode->nextNode = nullptr;

    if (_pList->count == 0)
    {
        _pList->headNode = pNode;
    }
    else
    {
        LNode *currentNode = _pList->headNode;

        while (currentNode->nextNode != nullptr)
            currentNode = currentNode->nextNode;
        currentNode->nextNode = pNode;
    }

    _pList->count++;
};

void ReleaseList(LinkedList *_pList)
{
    LNode *currentNode = _pList->headNode;
    while (currentNode != nullptr)
    {
        LNode *nextNode = currentNode->nextNode;
        free(_pList->headNode);
        currentNode = nextNode;
    }
};

void LPushList(LinkedList *_pList, int data)
{
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    newNode->data = data;
    newNode->nextNode = _pList->headNode ? _pList->headNode : nullptr;
    _pList->headNode = newNode;
    _pList->count++;
};

// main.cpp

#include <stdio.h>
#include <iostream>
#include "./include/LinkedList/linkedList.h"

using namespace std;

int main()
{
    LinkedList list = {};
    InitList(&list);

    PushList(&list, 100);
    PushList(&list, 200);
    PushList(&list, 300);

    ReleaseList(&list);
    
    return 0;
}