Data Structure

[Data Structure] Java ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ(LinkedList) ๊ตฌํ˜„

An effort will never betray ๐Ÿ˜Ž 2021. 1. 15. 10:55
๋ฐ˜์‘ํ˜•
  • ์ด ๊ธ€์€ "์˜จ๋ผ์ธ ์ž๋ฐ” ์Šคํ„ฐ๋”” ๋‚ด์šฉ"์„ ์ •๋ฆฌํ•œ ๊ธ€์ž…๋‹ˆ๋‹ค.

LinkedList๋ž€?

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

LinkedList ๊ตฌํ˜„

์ž๋ฐ”์—์„œ ์ธ์Šคํ„ด์Šค ์ „๋‹ฌ์€ ๋ ˆํผ๋Ÿฐ์Šค์ž…๋‹ˆ๋‹ค

public class ListNode {
    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        next = null;
    }
}

๋จผ์ € ListNode๋ฅผ ๊ตฌํ˜„ํ•˜์—ฌ data์™€ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” next๋ฅผ ๊ฐ€์ง€๋„๋ก ํด๋ž˜์Šค๋ฅผ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค.
๋‹ค์Œ ๋…ธ๋“œ๋กœ ์—ฐ๊ฒฐํ•˜์—ฌ ํ•˜๋‚˜์˜ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ƒ์„ฑํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  • ListNode add(ListNode head, ListNode nodeToAdd, int position) : head๋Š” ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์˜ ๋งจ ์•ž ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋ฉฐ nodeToAdd ๋…ธ๋“œ๋ฅผ ํ•ด๋‹น position์— ์ถ”๊ฐ€ํ•˜๋Š” ํ•จ์ˆ˜
  • ListNode remove(ListNode head, int positionToRemove) : ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์—์„œ positionToRemove์— ํ•ด๋‹นํ•˜๋Š” ์œ„์น˜์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์‚ญ์ œํ•˜๋Š” ํ•จ์ˆ˜
  • boolean contains(ListNode head, ListNode nodeTocheck) : ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์—์„œ nodeTocheck ๋…ธ๋“œ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
๋ฐ˜์‘ํ˜•