Qaupot Blog
Software Engineering, Trip

103. Linked List

๐Ÿ• Wed, 26 Feb 2014 09:00:00 GMT

Linked List

Linked List๋Š” ์—ฌ๋Ÿฌ Node๋“ค์„ ์ผ๋ จ์˜ ์ˆœ์„œ๋ฅผ ๊ฐ€์ง€๋Š” ํ˜•ํƒœ๋กœ ๋ณด๊ด€ํ•˜๋Š” ์ปจํ…Œ์ด๋„ˆ์ž…๋‹ˆ๋‹ค.
Node๋ฅผ ์ถ”๊ฐ€ ๋ฐ ์‚ญ์ œ์‹œ์— ์ž๋ฃŒ ์ „์ฒด๋ฅผ ์žฌ ์ •๋ ฌํ•  ํ•„์š”๊ฐ€ ์—†์œผ๋ฉฐ,
๊ณ ์ •๋œ ํฌ๊ธฐ๊ฐ€ ์—†์ด Node์˜ ์ถ”๊ฐ€ ์‚ญ์ œ์— ๋”ฐ๋ผ ํฌ๊ธฐ๊ฐ€ ์ฆ๊ฐ€ํ•˜๊ฑฐ๋‚˜ ๋Š˜์–ด๋‚˜๋ฏ€๋กœ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„์‹œ ๋ณด๊ด€ ๋ฐ์ดํ„ฐ์˜ ์–‘์„ ์˜ˆ์ธกํ•˜์—ฌ ์ œํ•œํ•  ํ•„์š”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

์–ด๋– ํ•œ ํ˜•ํƒœ๋กœ Node๋“ค์„ ์—ฐ๊ฒฐํ•˜์˜€๋Š”์ง€์— ๋”ฐ๋ผ ์„ฑ๋Šฅ์ด๋‚˜ ์‚ฌ์šฉ๋ฐฉ๋ฒ•์ด ์กฐ๊ธˆ์”ฉ ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค.
์ฃผ๋กœ ์‚ฌ์šฉ๋˜๋Š” ํ˜•ํƒœ๋Š” Single Linked List, Doubly Linked List, Circular Linked list์ž…๋‹ˆ๋‹ค.
์—ฐ๊ฒฐ๋œ ์ „์ฒด List์ค‘์—์„œ ๊ฐ€์žฅ ์ฒซ ๋…ธ๋“œ๋ฅผ Head, ๋ ๋…ธ๋“œ๋ฅผ Tail์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.

Singly Linked List

๋‹จ์ผ ์ง„ํ–‰ ๋ฐฉํ–ฅ์„ ๊ฐ€์ง€๋Š” Linked List์ž…๋‹ˆ๋‹ค.

2๋ฒˆ Node์—์„œ 3๋ฒˆ Node๋ฅผ ํƒ์ƒ‰ํ•  ์ˆ˜๋Š” ์žˆ์ง€๋งŒ, 1๋ฒˆ Node๋ฅผ ํƒ์ƒ‰ํ•  ์ˆ˜๋Š” ์—†์Šต๋‹ˆ๋‹ค.
1๋ฒˆ Node๋กœ ๋˜๋Œ์•„ ๊ฐ€๋ ค๋ฉด, ๋‹ค์‹œ ์ฒ˜์Œ๋ถ€ํ„ฐ Node๋ฅผ ํƒ์ƒ‰ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

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

์ฝ”๋“œ๋กœ Node๋ฅผ ํ‘œํ˜„ํ•˜๋ฉด ์œ„์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

Doubly Linked List

์–‘๋ฐฉํ–ฅ์œผ๋กœ ์ง„ํ–‰ํ•  ์ˆ˜ ์žˆ๋Š” Linked List์ž…๋‹ˆ๋‹ค.

2๋ฒˆ Node์—์„œ 3๋ฒˆ Node๋‚˜ 1๋ฒˆ Node ๋ชจ๋‘ ํƒ์ƒ‰ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

struct Node
{
    int value;
    Node *prev, *next;
};

์ฝ”๋“œ๋กœ Node๋ฅผ ํ‘œํ˜„ํ•˜๋ฉด ์œ„์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.
Singly Linked List์— ๋น„ํ•ด ์–‘ ๋ฐฉํ–ฅ์œผ๋กœ ์ง„ํ–‰ํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋˜์—ˆ์œผ๋‚˜,
๊ฐ Node์— ์†Œ์š”๋˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ๋น„์šฉ์ด ์ฆ๊ฐ€ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

Circular Linked list

์ˆœํ™˜ ํ˜•ํƒœ์˜ Linked List์ž…๋‹ˆ๋‹ค.
Singly Linked List ํ˜น์€ Doubly Linked List๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๋ช…์‹œ์ ์œผ๋กœ Head์™€ Tail์ด ์ง€์ •๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์— ์œ„์˜ ๋‘ ๊ฒฝ์šฐ๋ณด๋‹ค๋Š” ํŠน์ˆ˜ํ•œ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค.

class Node
{
private:
    int value;
    Node* nextPtr;
public:
    Node(int val)
        : value(val), nextPtr(nullptr) {}

    void Insert(Node* newNext)
    {
        if (nextPtr != nullptr)
            newNext->nextPtr = nextPtr;
        else
            newNext->nextPtr = nullptr;

        nextPtr = newNext;
    }

    Node* Find(int value)
    {   
        for (auto ptr = this; ptr != nullptr ; ptr = ptr->nextPtr)
        {
            std::cout << "Find Logger : " << ptr->value << std::endl;
            if (ptr->value == value)
                return ptr;
        }
        return nullptr;     
    }
};

int main(int argc, char** argv)
{
    Node headNode(4);

    headNode.Insert(new Node(20));
    headNode.Insert(new Node(23));
    headNode.Insert(new Node(12));

    if (headNode.Find(20) == nullptr)
        std::cout << "Success." << std::endl;
    else
        std::cout << "Fail." << std::endl;

    return 0;
}

Singly Linked List๋ฅผ ์‚ฌ์šฉํ•œ ๋‹จ์ˆœํ•œ ๋…ธ๋“œ ์ถ”๊ฐ€์™€ ์ˆœ์ฐจ๊ฒ€์ƒ‰ ์˜ˆ์ œ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.
nextPtr์ด nullptr์ผ ๊ฒฝ์šฐ Tail Node๋กœ ์ทจ๊ธ‰ํ•ฉ๋‹ˆ๋‹ค.

STL์—์„œ๋Š” listํ—ค๋”์— std::list๋ผ๋Š” ํ…œํ”Œ๋ฆฟ ํด๋ž˜์Šค๊ฐ€ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.
์ด ํด๋ž˜์Šค๋Š” Doubly Linked List๋กœ ๊ตฌํ˜„๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ธ”๋กœ๊ทธ๋Š” ๊ฐœ์ธ ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค. ๊ฒŒ์‹œ๊ธ€์€ ์˜ค๋ฅ˜๋ฅผ ํฌํ•จํ•˜๊ณ  ์žˆ์„ ์ˆ˜ ์žˆ์ง€๋งŒ, ์ €์ž๋Š” ์˜ค๋ฅ˜๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ๋…ธ๋ ฅํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.
๊ฒŒ์‹œ๊ธ€์— ๋ณ„๋„์˜ ๊ณ ์ง€๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ, ํฌ๋ฆฌ์—์ดํ‹ฐ๋ธŒ ์ปค๋จผ์ฆˆ ์ €์ž‘์žํ‘œ์‹œ-๋น„์˜๋ฆฌ-๋ณ€๊ฒฝ๊ธˆ์ง€ 4.0 ๋ผ์ด์„ ์Šค๋ฅผ ๋”ฐ๋ฆ…๋‹ˆ๋‹ค.

This blog is personal blog. published posts may contain some errors, but author doing efforts to clear errors.
If post have not notice of license, it under creative commons Attribution-NonCommercial-NoDerivatives 4.0.