[자.알.인] CH08. 연결 리스트

1. 연결 리스트(Linked List)란?

자료구조 형식

• 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로, 다양한 추상 자료형 구현의 기반이 된다.

 

연결 리스트

• 순서대로 저장하는 배열과 다르게 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.
• 어떤 데이터 덩어리(이하 노드(Node))를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다.
• 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.
• 특정 인덱스에 접근하려고 할 때 전체를 순서대로 읽어야 하기 때문에 시간 복잡도는 O(n) 이다.
• 반면, 시작/끝 지점에 엘리멘트를 추가, 삭제, 추출하는 작업의 시간 복잡도는 O(1) 이다.

2. 자.알.인에서의 연결 리스트 문제

• 위의 설명에서 '어떤 데이터 덩어리'를 저장 할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식 이라는 객체를 만들어야 했습니다.
• 자.알.인에서 사용해야하는 'ListNode' 라는 커스텀 객체를 만들게 되었습니다.

import java.util.Objects;

public class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public static ListNode of(int... integers) {
        if (integers == null || integers.length == 0) throw new IllegalArgumentException();

        ListNode head = new ListNode(0);
        ListNode last = head;
        ListNode p;
        for (int integer : integers) {
            p = new ListNode(integer);
            last.next = p;
            last = last.next;
        }

        return head.next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof ListNode)) return false;
        ListNode listNode = (ListNode) o;
        return val == listNode.val &&
                Objects.equals(next, listNode.next);
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, next);
    }

}

• https://jaime-note.tistory.com/66 를 참고하여 만들었습니다. of 기능을 추가하여 기본 예제의 값을 한번에 넣을 수 있도록 설정했습니다.
• ListNode 자체를 어떻게 사용해야 할지 처음에는 감이 안 잡혔으나 풀어 본 결과로는 선형 자료구조이기 때문에 배열과 다르게 Index를 꺼내는 형식이 아니라 새 ListNode 객체를 꺼내어 next라는 이름을 붙이며 원형 ListNode를 갱신하는 식이었습니다. 마치 for문 문제에서 temp라는 타입을 통해 순서를 변경하는 것과 같은 느낌입니다.

3. 본인이 알고 있는 문제의 연결 리스트

• Java에서 연결 리스트라고 생각이 떠오르는 건 'LinkedList' 를 떠오르게 되었습니다.
• LinkedList는 Collection 프레임워크의 일부이며 java.util 패키지에 속되어 있습니다.

// LinkedList 내의 Node 클래스

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

• 안에 Node(데이터 덩어리)가 있으며 위의 개념을 따라 사용되고 있습니다. 다만 prev라는 개념도 추가되어 앞/뒤의 Node 객체를 확인 할 수 있습니다.
• 풀어본 문제에서 매우 쉬운 방법으로는 LinkedList<Integer>로 Input 값을 정의하는 것이었습니다. Deque의 First와 Last를 사용할 수 있어 ListNode처럼 수동적이지 않고 앞, 뒤의 값을 추가, 삭제, 추출이 가능했습니다. (Ex. addFirst(E), addLast(E),  pollFirst(), pollLast(), peekFirst(), peekLast())
• 좀 더 이를 이용해 상세하게 풀려면 10장의 Deque, 우선순위 큐에서 다뤄봐야할 내용이기에 나중에 정리 할 수 있으면 블로그에 남기겠습니다.
• 공식문서 :
  • https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

LinkedList (Java Platform SE 8 )