Post

[JAVA] LinkedList

Posted Updated
By 9osari
18 min read
[JAVA] LinkedList

노드(Node)

배열은 크기를 미리 지정해야 하며, 중간에 데이터를 삽입/삭제할 때 성능에 제약이 있음.

이를 해결하기 위해 동적으로 메모리를 확보하고, 각 데이터를 노드(Node)로 만들어 연결하는 구조가 연결 리스트(Linked List)다.

  • 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
  • 각각의 노드가 참조를 통해 연결(Link) 되어 있다.
  • 배열처럼 미리 메모리를 할당하지 않아 낭비가 없다는 장점이 있지만, 각 노드가 다음 노드를 가리키기 위한 포인터를 가지고 있어 추가적인 메모리 오버헤드는 존재
  • 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라 한다.

연결 리스트(LinkedList)

직접 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class MyNode {
    //단방향 연결 리스트(Singly Linked List)
    Object data; //노드가 가지는 실제 값
    MyNode next; //다음 노드를 가리키는 참조(포인터)
    //앞 노드도 알고 있는건 양방향 연결 리스트(Doubly Linked List)
    //MyNode prev;

    public MyNode(Object data) {
        this.data = data;
    }

    //[A->B->C]
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        MyNode x = this;
        sb.append("[");
        while (x != null) {
            sb.append(x.data);
            if (x.next != null) {
                sb.append("->");
            }
            x = x.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

public class MyLinkedList {

    private MyNode head; // 연결 리스트의 첫 번째 노드를 가리키는 참조 (시작점)
    private int size;

    //입력받은 순서의 노드를 가져옴
    public Object get(int index) {
        MyNode x = getNode(index);
        return x.data;
    }

    //입력받은 순서와 데이터를 삽입
    public Object set(int index, Object e) {
        MyNode x = getNode(index);
        Object oldValue = x.data;
        x.data = e;
        return oldValue;
    }

    //index번째 노드 삭제
    public Object remove(int index) {
        MyNode x = getNode(index); //삭제할 노드 가져옴
        Object oldValue = x.data; //그 노드의 data를 oldValue에 저장
        if(index == 0) { //삭제노드가 첫번째면
            head = head.next; //head를 다음 노드로 이동시킴
        } else {
            MyNode prev = getNode(index - 1); //이전 노드를 가져와
            prev.next = x.next; //이전 노드가 삭제 대상의 다음 노드를 가리키게 만듦
        }
        x.next = null; //삭제 노드의 next 참조를 끊어 메모리 누수 방지
        size--; //리스트 크기 감소
        return oldValue; //삭제된 노드의 데이터 반환
    }

    //맨 끝에 새로운 노드를 추가
    public void add(Object e) {
        MyNode newNode = new MyNode(e); //1. 입력받은 e로 새 노드 생성 (item = e, next = null)
        if(head == null) { //2. 리스트가 비어있으면
            head = newNode; //3. 새 노드가 첫 노드가 됨
        } else {
            MyNode lastNode = getLastNode(); //4. 마지막 노드를 lastNode에 저장
            lastNode.next = newNode; // 5. 그 뒤에 새 노드를 연결
        }
        size++;
    }

    //index 위치에 새로운 노드 추가
    public void add(Object e, int index) {
        MyNode newNode = new MyNode(e); //새 노드 생성
        if(index == 0) {
            newNode.next = head;
            head = newNode; //새 노드가 첫 노드가 됨
        } else {
            MyNode prev = getNode(index -1); //새 노드를 넣을 직전 노드를 찾음
            newNode.next = prev.next; //새 노드의 next는 기존 prev 뒤의 노드로 연결
            prev.next = newNode;
        }
        size++;
    }

    //마지막 노드를 찾기
    public MyNode getLastNode() {
        MyNode x = head; //리스트의 첫 번째 노드인 head를 x에 저장
        while(x.next != null) { //x가 마지막이 아닐때까지 반복
            x = x.next;
        }
        return x; //x는 마지막 노드 반환
    }

    //index 번째 있는 노드 찾기
    private MyNode getNode(int index) {
        MyNode x = head;
        for(int i= 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        MyNode x = head;
        while(x != null) {
            sb.append(x.data);
            if(x.next != null) {
                sb.append(", ");
            }
            x = x.next;
        }
        sb.append("]");
        sb.append(" size = " + size);
        return sb.toString();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public static void main(String[] args) {
  MyLinkedList list = new MyLinkedList();
  //노드 추가
  list.add("a");
  list.add("b");
  list.add("c");
  list.add("d");
  list.add("e");
  System.out.println(list);

  //노드 덮어쓰기
  list.set(1, "z");
  System.out.println(list);

  //1번째 노드 찾기
  System.out.println(list.get(0));

  //1번째 노드 삭제
  list.remove(0);
  System.out.println(list);

  //마지막 노드 찾기
  MyNode lastNode = list.getLastNode();
  System.out.println(lastNode);

  //사이즈 확인
  int size = list.size();
  System.out.println(size);

  //2번째에 노드 넣기
  list.add("f", 2);
  System.out.println(list);
}

//출력
[a, b, c, d, e] size = 5
[a, z, c, d, e] size = 5
a
[z, c, d, e] size = 4
[e]
4
[z, c, f, d, e] size = 5
  • 연결 리스트는 데이터를 추가할 때 마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제가 발생하지 않는다.

배열 위치별 데이터 추가/삭제

첫 번째 위치에 데이터 추가

  • 배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지는 어떤 일이 일어난지도 모른다.
  • 연결 리스트의 첫 번째 항목에 값을 추가하는 것은 빠르다. O(1)

첫 번째 위치의 데이터 삭제

  • 노드 삭제 후 오른쪽 노드의 index 가 하나씩 당겨진다.
  • 배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 밀어야 하지만 연결리스트는 일부 참조만 변경하면 된다.
  • 연결 리스트의 첫 번쨰 항목에 값을 삭제하는 것은 빠르다. O(1)

중간 위치에 데이터 추가

  • 추가한 노드 오른쪽에 있는 노드들의 index 가 하나씩 뒤로 밀린다.
  • 배열의 경우 데이터가 추가되면 인덱스 위치 부터 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다.
  • 위치를 찾는데 O(n), 위치를 찾아 노드를 추가하는데 O(1) 따라서 둘을 합하면 O(n)

중간 위치에 데이터 삭제

  • 오른쪽 노드의 index 가 하나씩 당겨진다.
  • 연결리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)
  • 항목을 삭제하는데 O(1) 둘을 합하면 O(n)

연결 리스트와 배열 리스트 둘다 중간에 있는 항목을 추가하거나 삭제하는 경우 둘다 같은 O(n)

기능 배열 리스트 (ArrayList) 연결 리스트 (LinkedList)
인덱스 조회 O(1) O(n)
검색 O(n) O(n)
앞에 추가/삭제 O(n) O(1)
뒤에 추가/삭제 O(1) O(n)
평균 추가/삭제 O(n) O(n)


배열 리스트(ArrayList)와 연결 리스트(LinkedList)

데이터를 자주 조회하거나, 뒤쪽에 추가할 일이 많다면 ArrayList가 더 효율적이다. 반면, 앞쪽에서 삽입이나 삭제가 자주 발생한다면 LinkedList가 더 나은 선택이다.

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트(Doubly Linked List)는 각 노드가 prev와 next 모두를 가지기 때문에 양방향 탐색이 가능하다. 삽입/삭제 시, 이전 노드를 따로 찾을 필요가 없어 성능상 이점이 있다. 단, 포인터가 2개이므로 메모리 사용량은 더 많다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class MyNode {
    //단방향 연결 리스트(Singly Linked List)
    Object data; //노드가 가지는 실제 값
    MyNode next; //다음 노드를 가리키는 참조(포인터)
    //앞 노드도 알고 있는건 양방향 연결 리스트(Doubly Linked List)
    MyNode prev;
}

//마지막 노두를 참조하는 연결 리스트
public class LinkedList {
		private Node first;
		private Node last; //마지막 노드 참조
		private int size = 0;
}
  • 노드를 앞 뒤로 모두 연결하는 이중 연결 리스트를 사용해 성능을 좀 더 개선할 수 있다.
  • 자바가 제공하는 연결 리스트는 prev/ next 를 모두 가지는 이중 연결 리스트로 구현되어 있으며 first/last/포인터 까지 유지하기 때문에 맨 앞/뒤 삽입/삭제는 O(1)의 성능을 보장한다.

연결 리스트는 삽입/삭제가 자주 발생하는 구조에 적합한 자료구조다. 반면, 조회와 마지막 위치 추가가 많다면 배열 리스트가 더 효율적이다. 실무에서는 두 구조의 장단점을 파악해 상황에 맞는 선택이 중요하다.

제네릭 도입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

public class MyLinkedListV2<E> {

    private MyNode<E> head; // 연결 리스트의 첫 번째 노드를 가리키는 참조 (시작점)
    private int size;

    //입력받은 순서의 노드를 가져옴
    public E get(int index) {
        MyNode<E> x = getNode(index);
        return x.data;
    }

    //입력받은 순서와 데이터를 삽입
    public E set(int index, E e) {
        MyNode<E> x = getNode(index);
        E oldValue = x.data;
        x.data = e;
        return oldValue;
    }

    //index번째 노드 삭제
    public E remove(int index) {
        MyNode<E> x = getNode(index); //삭제할 노드 가져옴
        E oldValue = x.data; //그 노드의 data를 oldValue에 저장
        if(index == 0) { //삭제노드가 첫번째면
            head = head.next; //head를 다음 노드로 이동시킴
        } else {
            MyNode<E> prev = getNode(index - 1); //이전 노드를 가져와
            prev.next = x.next; //이전 노드가 삭제 대상의 다음 노드를 가리키게 만듦
        }
        x.next = null; //삭제 노드의 next 참조를 끊어 메모리 누수 방지
        size--; //리스트 크기 감소
        return oldValue; //삭제된 노드의 데이터 반환
    }

    //맨 끝에 새로운 노드를 추가
    public void add(E e) {
        MyNode<E> newNode = new MyNode<>(e); //1. 입력받은 e로 새 노드 생성 (item = e, next = null)
        if(head == null) { //2. 리스트가 비어있으면
            head = newNode; //3. 새 노드가 첫 노드가 됨
        } else {
            MyNode<E> lastNode = getLastNode(); //4. 마지막 노드를 lastNode에 저장
            lastNode.next = newNode; // 5. 그 뒤에 새 노드를 연결
        }
        size++;
    }

    //index 위치에 새로운 노드 추가
    public void add(E e, int index) {
        MyNode<E> newNode = new MyNode<>(e); //새 노드 생성
        if(index == 0) {
            newNode.next = head;
            head = newNode; //새 노드가 첫 노드가 됨
        } else {
            MyNode<E> prev = getNode(index -1); //새 노드를 넣을 직전 노드를 찾음
            newNode.next = prev.next; //새 노드의 next는 기존 prev 뒤의 노드로 연결
            prev.next = newNode;
        }
        size++;
    }

    //마지막 노드를 찾기
    public MyNode<E> getLastNode() {
        MyNode<E> x = head; //리스트의 첫 번째 노드인 head를 x에 저장
        while(x.next != null) { //x가 마지막이 아닐때까지 반복
            x = x.next;
        }
        return x; //x는 마지막 노드 반환
    }

    //index 번째 있는 노드 찾기
    private MyNode<E> getNode(int index) {
        MyNode<E> x = head;
        for(int i= 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    public int size() {
        return size;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        MyNode x = head;
        while(x != null) {
            sb.append(x.data);
            if(x.next != null) {
                sb.append(", ");
            }
            x = x.next;
        }
        sb.append("]");
        sb.append(" size = " + size);
        return sb.toString();
    }

    private static class MyNode<E> {
        E data;
        MyNode<E> next;

        public MyNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return String.valueOf(data);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public static void main(String[] args) {
    MyLinkedListV2<String> stringList = new MyLinkedListV2<>();

    stringList.add("a");
    stringList.add("b");
    stringList.add("c");
    System.out.println( stringList);

    stringList.remove(0);
    System.out.println( stringList);

    stringList.add("a",0);
    System.out.println( stringList);

    stringList.set(2, "z");
    System.out.println( stringList);

    System.out.println("----------------");
    MyLinkedListV2<Integer> intList = new MyLinkedListV2<>();
    intList.add(1);
    intList.add(2);
    intList.add(3);
    System.out.println( intList);

    intList.remove(0);
    System.out.println( intList);

    intList.add(1,0);
    System.out.println( intList);

    intList.set(2, 99);
    System.out.println( intList);
}

//실행결과
[a, b, c] size = 3
[b, c] size = 2
[a, b, c] size = 3
[a, b, z] size = 3
----------------
[1, 2, 3] size = 3
[2, 3] size = 2
[1, 2, 3] size = 3
[1, 2, 99] size = 3
  • 기존 MyLinkedList는 Object 타입으로 모든 데이터를 처리함 → 타입 안정성이 없음
  • Object로 받아서 사용하면 형변환(casting)이 필요하고, 런타임 오류 발생 가능성 있음
  • 제네릭을 도입하면 컴파일 타임에 타입을 강제할 수 있어서, 타입 안전성을 확보하고 불필요한 캐스팅도 제거 가능
  • String 전용 리스트, Integer 전용 리스트처럼 각각 타입을 제한할 수 있음

제네릭은 타입 안정성과 재사용성을 모두 향상시키는 훌륭한 도구이며, 실무에서 컬렉션, 유틸리티 클래스 등을 만들 때 거의 필수적으로 사용됨.



출처: 김영한의 실전 자바 - 중급 2편

java
java 김영한-JAVA-중급
This post is licensed under CC BY 4.0 by the author.