๐Ÿ”— Linked List

hyukimยท2020๋…„ 5์›” 5์ผ
0

๋ฐ์ดํ„ฐ๊ตฌ์กฐ๋ก 

๋ชฉ๋ก ๋ณด๊ธฐ
3/6

Linked List

์—ฐ์†์ ์ธ ๋ฐ์ดํ„ฐ๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์—๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ๋ฐฐ์—ด์ด ์žˆ์„ ์ˆ˜๋„ ์žˆ๊ณ , ์–ด๋ ˆ์ด ๋ฆฌ์ŠคํŠธ, ๋ฒกํ„ฐ, ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ ๋“ฑ์ด ์žˆ๋‹ค. ์ด๋ฒˆ์—” ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ(์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ)์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ๋‹ค.

๊ฐœ๋…

  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ๋ฐฐ์—ด๊ณผ ๊ฐ™์ด ์—ฌ๋Ÿฌ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†์ ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ค‘ ํ•˜๋‚˜์ด๋‹ค.
  • ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด๋Š” ๋…ธ๋“œ๋“ค๋กœ ๊ตฌ์„ฑ์ด ๋œ๋‹ค.
  • ๋…ธ๋“œ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐ์ดํ„ฐ ํ•„๋“œ์™€ ๋‹ค์Œ ๋…ธ๋“œ์˜ ์ฃผ์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋งํฌ ํ•„๋“œ๋กœ ๊ตฌ์„ฑ๋œ๋‹ค.
  • ๋…ธ๋“œ์˜ ์ข…๋ฅ˜๋Š” ๋ฆฌ์ŠคํŠธ์˜ ์‹œ์ž‘์ธ ํ—ค๋“œ ๋…ธ๋“œ(Head Node)์™€ ๋ฆฌ์ŠคํŠธ์˜ ๋์ธ ํ…Œ์ผ ๋…ธ๋“œ(Tail Node), ๊ทธ ์™ธ์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค.
  • ํ—ค๋“œ ๋…ธ๋“œ๋Š” ๊ตฌํ˜„์— ๋”ฐ๋ผ ๋ฐ์ดํ„ฐ ํ•„๋“œ๊ฐ€ ์žˆ์„ ์ˆ˜๋„ ์žˆ๊ณ  ์—†์„ ์ˆ˜๋„ ์žˆ๋‹ค.
  • ํ…Œ์ผ ๋…ธ๋“œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋งํฌ์˜ ๊ฐ’์ด NULL์ด๋‹ค. (NULL์„ ๊ฐ€๋ฆฌํ‚จ๋‹ค.)

ํŠน์ง• (์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ vs ๋ฐฐ์—ด)

  • ๋ฐฐ์—ด์ด๋ผ๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๊ฐ€ ์žˆ๋Š”๋ฐ ์™œ ๊ตณ์ด ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด์„œ ์“ธ๊นŒ?
  • ๊ฐ€๋ณ€๊ธธ์ด : ํ•„์š”์— ๋”ฐ๋ฅธ ๋™์ ์ธ ํ• ๋‹น์ด ๊ฐ€๋Šฅํ•˜๋‹ค. ๋ฐฐ์—ด์€ ์ปดํŒŒ์ผ ํƒ€์ž„ ์ „์— ํฌ๊ธฐ๊ฐ€ ๋ฏธ๋ฆฌ ์ •ํ•ด์ ธ ์žˆ์ง€๋งŒ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” ํ•„์š”์— ๋”ฐ๋ผ ์ถ”๊ฐ€ํ•˜๊ณ  ์‚ญ์ œํ•  ์ˆ˜๊ฐ€ ์žˆ์–ด์„œ ์œ ์—ฐํ•œ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. โ†’ ์‚ฌ์‹ค์ƒ ๋ฐฐ์—ด๊ณผ ๊ฐ€์žฅ ํฐ ์ฐจ์ด
  • ์ถ”๊ฐ€, ์‚ญ์ œ๊ฐ€ ๋น ๋ฆ„ : ๋ฐฐ์—ด์˜ ๊ฒฝ์šฐ๋Š” ์ถ”๊ฐ€, ์‚ญ์ œ๊ฐ€ ๋ถˆ๊ฐ€๋Šฅ ํ•˜๋ฏ€๋กœ ArrayList์™€ ๋น„๊ต๋ฅผ ํ•˜๋ฉด ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋” ๋น ๋ฅด๋‹ค
  • ์ธ๋ฑ์Šค ์ ‘๊ทผ ๋Š๋ฆผ : ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋Š” n๋ฒˆ์งธ ์š”์†Œ์— ์ ‘๊ทผํ•˜๋ ค๋ฉด ์ˆœ์„œ๋Œ€๋กœ ๋…ธ๋“œ๋ฅผ ์ฐพ์•„๊ฐ€์•ผ ํ•˜๋ฏ€๋กœ(O(n)) ๋ฐฐ์—ด์— ๋น„ํ•ด ์ธ๋ฑ์Šค ์ ‘๊ทผ์ด ๋Š๋ฆฌ๋‹ค. ๋ฐฐ์—ด์€ ์‹œ์ž‘ ์ฃผ์†Œ์™€ ์˜คํ”„์…‹์„ ํ†ตํ•ด ์ธ๋ฑ์Šค์˜ ๋น ๋ฅธ ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•˜๋‹ค(O(1)).

์ข…๋ฅ˜

๋‹จ์ˆœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Singly Linked List)

  • ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์ด๋‹ค.
  • ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” t_list *next์™€ ๋ฐ์ดํ„ฐ ํ•„๋“œ๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค.
  • ๋งจ ๋’ค์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์กฐํšŒํ•  ๋•Œ๋Š” size ๋งŒํผ์˜ ์‹œ๊ฐ„์ด ํ•„์š”ํ•˜๋‹ค.
  • ์ •์˜ ๊ตฌํ˜„
typedef struct s_list
{
	void *data;
	struct s_list *next;
} t_list;

์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Doubly Linked List)

  • ํ•œ ๋…ธ๋“œ์—์„œ ๋งํฌ๊ฐ€ ์–‘๋ฐฉํ–ฅ(์ด์ „, ๋‹ค์Œ)์œผ๋กœ ์—ฐ๊ฒฐ ๋ผ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ๋‹ค.
  • ๊ฐ€์žฅ ํฐ ์žฅ์ ์€ ๋…ธ๋“œ ํƒ์ƒ‰์ด ์–‘๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ์ ์ด๋‹ค.
  • ์ธ๋ฑ์Šค ์ ‘๊ทผ์„ ํ•  ๋•Œ, 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)

  • ๋‹จ๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ ํ…Œ์ผ ๋…ธ๋“œ์˜ next๊ฐ€ ํ—ค๋“œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํ˜•ํƒœ์ด๋‹ค.
  • ๋ชจ๋“  ๋…ธ๋“œ์˜ ๋งํฌ ํ•„๋“œ์˜ ๊ฐ’์ด NULL์ด ์•„๋‹ˆ๋‹ค.
  • ๊ฒ€์ƒ‰์„ ํ•˜๋‹ค๊ฐ€ ์ค‘๋‹จํ•œ ์œ„์น˜์—์„œ ๊ฒ€์ƒ‰์„ ์ด์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค.
  • ์ •์˜ ๊ตฌํ˜„
typedef struct s_clist
{
	void *data;
	struct s_clist *next;
} t_clist;

์›ํ˜• ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Doubly Circular Linked List)

  • ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์—์„œ ํ…Œ์ผ ๋…ธ๋“œ์˜ next๊ฐ€ ํ—ค๋“œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ํ˜•ํƒœ์ด๋‹ค.
  • ๋ชจ๋“  ๋…ธ๋“œ์˜ ๋งํฌ ํ•„๋“œ๊ฐ€ NULL์ด ์•„๋‹ˆ๋‹ค.
  • ๊ธฐ๋ณธ ๋ฆฌ์ŠคํŠธ์— ๋น„ํ•ด ์ ‘๊ทผ์„ฑ์ด ๋›ฐ์–ด๋‚˜๋‹ค.
  • ์ •์˜ ๊ตฌํ˜„
typedef struct s_dclist
{
	void *data;
	struct s_dclist *prev;
	struct s_dclist *next;
} t_dclist;
profile
๐Ÿ’ช ๐Ÿฅฉ ๐Ÿบ โœˆ ๐Ÿ’ป

0๊ฐœ์˜ ๋Œ“๊ธ€