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๋ก ๊ตฌํ๋์ด ์์ต๋๋ค.