Linked List
์ฐ์์ ์ธ ๋ฐ์ดํฐ๋ฅผ ํํํ๋ ๋ฐฉ๋ฒ์๋ ์ฌ๋ฌ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ ์ ์๋ค. ๋ฐฐ์ด์ด ์์ ์๋ ์๊ณ , ์ด๋ ์ด ๋ฆฌ์คํธ, ๋ฒกํฐ, ๋งํฌ๋ ๋ฆฌ์คํธ ๋ฑ์ด ์๋ค. ์ด๋ฒ์ ๋งํฌ๋ ๋ฆฌ์คํธ(์ฐ๊ฒฐ ๋ฆฌ์คํธ)์ ๋ํด ์์๋ณด๊ฒ ๋ค.
![](https://velog.velcdn.com/images%2Fdavkim1030%2Fpost%2Fc20830e0-be90-40c9-8b74-65e078842c72%2Fimage.png)
๊ฐ๋
- ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ๋ฐฐ์ด๊ณผ ๊ฐ์ด ์ฌ๋ฌ ๋ฐ์ดํฐ๋ฅผ ์ฐ์์ ์ผ๋ก ๋ํ๋ด๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ ์ค ํ๋์ด๋ค.
- ๋ฐ์ดํฐ๋ฅผ ๋ด๋ ๋
ธ๋๋ค๋ก ๊ตฌ์ฑ์ด ๋๋ค.
- ๋
ธ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๋ฐ์ดํฐ ํ๋์ ๋ค์ ๋
ธ๋์ ์ฃผ์๋ฅผ ๊ฐ๋ฆฌํค๋ ๋งํฌ ํ๋๋ก ๊ตฌ์ฑ๋๋ค.
- ๋
ธ๋์ ์ข
๋ฅ๋ ๋ฆฌ์คํธ์ ์์์ธ ํค๋ ๋
ธ๋(Head Node)์ ๋ฆฌ์คํธ์ ๋์ธ ํ
์ผ ๋
ธ๋(Tail Node), ๊ทธ ์ธ์ ๋
ธ๋๊ฐ ์๋ค.
- ํค๋ ๋
ธ๋๋ ๊ตฌํ์ ๋ฐ๋ผ ๋ฐ์ดํฐ ํ๋๊ฐ ์์ ์๋ ์๊ณ ์์ ์๋ ์๋ค.
- ํ
์ผ ๋
ธ๋๋ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ๋งํฌ์ ๊ฐ์ด NULL์ด๋ค. (NULL์ ๊ฐ๋ฆฌํจ๋ค.)
ํน์ง (์ฐ๊ฒฐ ๋ฆฌ์คํธ vs ๋ฐฐ์ด)
- ๋ฐฐ์ด์ด๋ผ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๊ฐ ์๋๋ฐ ์ ๊ตณ์ด ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค์ด์ ์ธ๊น?
- ๊ฐ๋ณ๊ธธ์ด : ํ์์ ๋ฐ๋ฅธ ๋์ ์ธ ํ ๋น์ด ๊ฐ๋ฅํ๋ค. ๋ฐฐ์ด์ ์ปดํ์ผ ํ์ ์ ์ ํฌ๊ธฐ๊ฐ ๋ฏธ๋ฆฌ ์ ํด์ ธ ์์ง๋ง ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ํ์์ ๋ฐ๋ผ ์ถ๊ฐํ๊ณ ์ญ์ ํ ์๊ฐ ์์ด์ ์ ์ฐํ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ์ด ๊ฐ๋ฅํ๋ค. โ ์ฌ์ค์ ๋ฐฐ์ด๊ณผ ๊ฐ์ฅ ํฐ ์ฐจ์ด
- ์ถ๊ฐ, ์ญ์ ๊ฐ ๋น ๋ฆ : ๋ฐฐ์ด์ ๊ฒฝ์ฐ๋ ์ถ๊ฐ, ์ญ์ ๊ฐ ๋ถ๊ฐ๋ฅ ํ๋ฏ๋ก ArrayList์ ๋น๊ต๋ฅผ ํ๋ฉด ์ฐ๊ฒฐ๋ฆฌ์คํธ๊ฐ ๋ ๋น ๋ฅด๋ค
- ์ธ๋ฑ์ค ์ ๊ทผ ๋๋ฆผ : ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ n๋ฒ์งธ ์์์ ์ ๊ทผํ๋ ค๋ฉด ์์๋๋ก ๋
ธ๋๋ฅผ ์ฐพ์๊ฐ์ผ ํ๋ฏ๋ก(O(n)) ๋ฐฐ์ด์ ๋นํด ์ธ๋ฑ์ค ์ ๊ทผ์ด ๋๋ฆฌ๋ค. ๋ฐฐ์ด์ ์์ ์ฃผ์์ ์คํ์
์ ํตํด ์ธ๋ฑ์ค์ ๋น ๋ฅธ ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ค(O(1)).
์ข
๋ฅ
๋จ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Singly Linked List)
![](https://velog.velcdn.com/images%2Fdavkim1030%2Fpost%2Faaaa6315-d941-4e54-aa94-03747022f007%2Fimage%201.png)
- ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ด๋ค.
- ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋
t_list *next
์ ๋ฐ์ดํฐ ํ๋๋ก ์ด๋ฃจ์ด์ง๋ค.
- ๋งจ ๋ค์ ๋ฐ์ดํฐ๋ฅผ ์กฐํํ ๋๋
size
๋งํผ์ ์๊ฐ์ด ํ์ํ๋ค.
- ์ ์ ๊ตฌํ
typedef struct s_list
{
void *data;
struct s_list *next;
} t_list;
์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Doubly Linked List)
![](https://velog.velcdn.com/images%2Fdavkim1030%2Fpost%2F7409537e-e87d-4a7e-adb1-62d65fcd3b7d%2Fimage%202.png)
- ํ ๋
ธ๋์์ ๋งํฌ๊ฐ ์๋ฐฉํฅ(์ด์ , ๋ค์)์ผ๋ก ์ฐ๊ฒฐ ๋ผ์๋ ๋ฆฌ์คํธ๋ค.
- ๊ฐ์ฅ ํฐ ์ฅ์ ์ ๋
ธ๋ ํ์์ด ์๋ฐฉํฅ์ผ๋ก ๊ฐ๋ฅํ๋ค๋ ์ ์ด๋ค.
- ์ธ๋ฑ์ค ์ ๊ทผ์ ํ ๋,
size / 2
์ด์์ ์ธ๋ฑ์ค๋ฅผ ์ ๊ทผํ ๊ฒฝ์ฐ, ๋ค์์๋ถํฐ ์ ๊ทผํ๋ฉด ๋๋ฏ๋ก ํ์ ์๊ฐ์ด ์ต๋ ๋ฐ๊น์ง ์ค์ด๋ ๋ค.
- ๋จ์ ์ ์ด์ ๋
ธ๋๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ๋ ๋ ์ด๋ค๋ ๊ฒ์ด๋ค.
- ๋งํฌ ํ๋๊ฐ
t_list *next
์ t_list *prev
๋ก ์ด๋ฃจ์ด์ง๋ค.
- ์ ์ ๊ตฌํ
typedef struct s_dlist
{
void *data;
struct s_dlist *prev;
struct s_dlist *next;
} t_sdlist;
์ํ ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Circular Linked List)
![](https://velog.velcdn.com/images%2Fdavkim1030%2Fpost%2Fea200d92-fb9d-4a62-94f0-bdb41647780c%2Fimage%203.png)
- ๋จ๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ํ
์ผ ๋
ธ๋์
next
๊ฐ ํค๋ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํํ์ด๋ค.
- ๋ชจ๋ ๋
ธ๋์ ๋งํฌ ํ๋์ ๊ฐ์ด NULL์ด ์๋๋ค.
- ๊ฒ์์ ํ๋ค๊ฐ ์ค๋จํ ์์น์์ ๊ฒ์์ ์ด์ด๊ฐ ์ ์๋ค.
- ์ ์ ๊ตฌํ
typedef struct s_clist
{
void *data;
struct s_clist *next;
} t_clist;
์ํ ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Doubly Circular Linked List)
![](https://velog.velcdn.com/images%2Fdavkim1030%2Fpost%2F4f71937a-fe9e-4102-bd2c-eb04538ee8d0%2Fimage%204.png)
- ์๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ํ
์ผ ๋
ธ๋์
next
๊ฐ ํค๋ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํํ์ด๋ค.
- ๋ชจ๋ ๋
ธ๋์ ๋งํฌ ํ๋๊ฐ NULL์ด ์๋๋ค.
- ๊ธฐ๋ณธ ๋ฆฌ์คํธ์ ๋นํด ์ ๊ทผ์ฑ์ด ๋ฐ์ด๋๋ค.
- ์ ์ ๊ตฌํ
typedef struct s_dclist
{
void *data;
struct s_dclist *prev;
struct s_dclist *next;
} t_dclist;