[Hackerrank 문제 풀이] Insert a Node Into a Sorted Doubly Linked List

Junu Kim·2025년 11월 8일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

36/46

[Linked List] Insert a Node Into a Sorted Doubly Linked List

난이도: ★☆☆☆☆ • solved on: 2025-11-08

문제 요약

문제 유형: Linked List (이중 연결 리스트)
요구사항: 정렬된 이중 연결 리스트(Doubly Linked List)에 주어진 데이터를 삽입해, 정렬 순서가 유지되도록 새 노드를 추가해야 한다.

사용 개념

자료구조
- DoublyLinkedListNode
  → prev와 next 포인터를 동시에 가지는 노드 구조
알고리즘/기법
- 순차 탐색(linear traversal)
- 포인터 조작(pointer manipulation)
핵심 키워드
- 삽입 위치 탐색
- prev / next 연결 관리
- 예외 처리 (맨 앞, 중간, 맨 뒤 삽입)

풀이 아이디어

문제 분해

삽입할 위치를 찾기 위해 리스트를 순회한다.

삽입 위치는 현재 노드의 값 ≤ data ≤ 다음 노드의 값인 곳이다.

새 노드를 중간에 넣을 때는 prev / next를 모두 재연결해야 한다.

맨 앞이나 맨 뒤 삽입 시 예외 처리를 별도로 수행한다.
핵심 로직 흐름
if (data <= head.data)
    // 맨 앞 삽입
else
    // 중간 또는 끝 탐색
    while (current != null)
        if (current.next == null)
            // 맨 뒤 삽입
        else if (current.data <= data <= current.next.data)
            // 중간 삽입
예외 처리

리스트의 맨 앞: 기존 head보다 작은 값일 때 새 노드를 head로 지정

리스트의 맨 뒤: 마지막 노드의 next가 null인 경우 연결 처리

코드

public static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode llist, int data) {
    DoublyLinkedListNode llistCurrent = llist;
    DoublyLinkedListNode newItem = new DoublyLinkedListNode(data);

    // Case 1: 맨 앞에 삽입
    if (data <= llist.data) {
        newItem.next = llist;
        llist.prev = newItem;
        return newItem;
    }

    // Case 2: 중간 또는 맨 뒤 탐색
    while (llistCurrent != null) {
        // 마지막 노드일 경우 (맨 뒤 삽입)
        if (llistCurrent.next == null) {
            llistCurrent.next = newItem;
            newItem.prev = llistCurrent;
            break;
        }

        // 중간 삽입
        if (llistCurrent.data <= data && data <= llistCurrent.next.data) {
            newItem.next = llistCurrent.next;
            llistCurrent.next.prev = newItem;

            llistCurrent.next = newItem;
            newItem.prev = llistCurrent;
            break;
        }
        llistCurrent = llistCurrent.next;
    }
    return llist;
}