[강의] 12월 4일 수업정리

LinkedList에 대한 수업을 들었다.

 

 

1. 연결 리스트 ( LinkedList )

1.1 ArrayList와의 차이점

 

1.1.1 메모리 관리

• ArrayList: 메모리 크기를 미리 지정하고, 필요 시 배열 크기를 조정한다.
• LinkedList: 메모리 크기를 미리 정하지 않고, 데이터가 추가될 때마다 동적으로 메모리를 할당한다.

1.1.2 구조

• ArrayList: 연속된 메모리 블록에 데이터를 저장하며, 인덱스를 통해 빠르게 접근 가능하다.
• LinkedList: 노드로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함한다.

1.1.3 인덱스 접근

• ArrayList는 인덱스를 통해 데이터에 직접 접근 가능하다.
• LinkedList도 특정 구현에서 인덱스를 사용할 수 있지만, 실제로는 순차적으로 노드를 따라가며 데이터를 찾는다.

 

1.2 LinkedList 설명

 

1.2.1 구조적 특징

• LinkedList는 헤드 노드(시작점)만 알고 있으며, 나머지 노드들은 포인터로 연결된다.
• 따라서 특정 데이터를 찾으려면 처음부터 순차적으로 탐색해야 한다.

1.2.2 검색 효율

• 데이터 검색은 순차 탐색 방식으로 이루어지며, 효율이 떨어진다.
• 하지만 삽입 및 삭제는 특정 위치에서 수행할 경우 효율이 좋다.

1.2.3 사용 사례

• 데이터의 순서가 중요하지 않거나, 삽입 및 삭제가 빈번히 발생하는 경우 적합하다.
• 특정 상황에서는 Queue, Stack 같은 자료 구조로도 사용 가능하다.

1.2.4 한계

• 순차 탐색만 가능하다는 점에서 검색 효율이 낮다.
• 따라서, 순회가 필수적인 경우에만 LinkedList의 사용이 권장된다.

 

1.3 LinkedList 구현 

 

1.3.1 간단 구현 

// LinkedList.h
#pragma once
#include <stdio.h>

class C_LINKEDLIST
{
private:
	struct S_NODE
	{
		int nData;
		S_NODE* pNext;
	};
private:
	S_NODE* m_pBegin;
private:
	S_NODE* createNode(int nData);
public:
	C_LINKEDLIST() = default;
	void pushBack(int nData);
	void print();
};

// LinkedList.cpp
#include "linkedlist.h"

C_LINKEDLIST::S_NODE* C_LINKEDLIST::createNode(int nData) // 정의가 없다고 하는데 S_NODE는 struct안에있으니 네임스페이스를 붙여야한다 C_LINKEDLIST:: 이거 누구인지에 대한 것 

{
    S_NODE* pNode = new S_NODE{};
    pNode->nData = nData;
    pNode->pNext = nullptr;
    
    return pNode;
}

void C_LINKEDLIST::pushBack(int nData)
{
    if (!m_pBegin)
    {
        m_pBegin = createNode(nData);
        return;
    }

    S_NODE* pNode = m_pBegin;
    while (pNode->pNext)
    {
        pNode = pNode->pNext;
    }
    pNode->pNext = createNode(nData);
}

void C_LINKEDLIST::print()
{
    S_NODE* pNode = m_pBegin;
    
    while (pNode)
    {
        printf("%d ", pNode->nData);
        pNode = pNode->pNext;
    }
    printf("\n");
}

// main.cpp
#include <iostream>
#include "linkedlist.h"

int main()
{
    C_LINKEDLIST cList{};

    cList.pushBack(1);
    cList.pushBack(2);
    cList.pushBack(3);
    cList.pushBack(4);
    cList.pushBack(5);

    cList.print();
}

 

 

1.3.2  완성본 

// LinkedList.h
#pragma once
#include <stdio.h>

class C_LINKEDLIST
{
private:
	struct S_NODE
	{
		int nData;
		S_NODE* pNext;
	};
private:
	S_NODE* m_pBegin;
	S_NODE* m_pEnd;
private:
	S_NODE* createNode(int nData);
public:
	C_LINKEDLIST() = default;
	void pushBack(int nData);
	void pushFront(int nData);
	void print();
};

// LinkedList.cpp
#include "linkedlist.h"

C_LINKEDLIST::S_NODE* C_LINKEDLIST::createNode(int nData)
{
    S_NODE* pNode = new S_NODE{};
    pNode->nData = nData;
    pNode->pNext = nullptr;
    
    return pNode;
}

//void C_LINKEDLIST::pushBack(int nData) // 요약하지 않은 코드 
//{

//    if (!m_pBegin)
//    {
//        m_pBegin = createNode(nData);
//        m_pEnd = m_pBegin;
//        return;
//    }
//    m_pEnd->pNext = createNode(nData);
//    m_pEnd = m_pEnd->pNext;
//}

void C_LINKEDLIST::pushBack(int nData) // 요약, 완전
{
    S_NODE* pNode = createNode(nData);

    if (!m_pBegin)
        m_pBegin = pNode;
    else
        m_pEnd->pNext = pNode;
   
    m_pEnd = pNode;
}

void C_LINKEDLIST::pushFront(int nData) // 앞에서 삽입
{
    S_NODE* pNode = createNode(nData);
    if (!m_pBegin)
        m_pEnd = pNode;
    else
        pNode->pNext = m_pBegin;

    m_pBegin = pNode;
}

void C_LINKEDLIST::print()
{
    S_NODE* pNode = m_pBegin;
    
    while (pNode)
    {
        printf("%d ", pNode->nData);
        pNode = pNode->pNext;
    }
    printf("\n");
}

// main.cpp
#include <iostream>
#include "linkedlist.h"

int main()
{
    C_LINKEDLIST cList{};

    cList.pushBack(1);
    cList.pushBack(2);
    cList.pushBack(3);
    cList.pushBack(4);
    cList.pushBack(5);

    cList.print();
}