[Linked List] Insert a Node at a Specific Position in a Linked List

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

---

문제 요약

• 문제 유형: 연결 리스트(Linked List), 포인터 조작
• 요구사항: 주어진 단일 연결 리스트(Singly Linked List)에서 지정된 위치에 새로운 노드를 삽입해야 한다.

---

사용 개념

1. 자료구조

   • SinglyLinkedListNode — 다음 노드를 가리키는 next 포인터를 가진 단일 연결 리스트 노드 구조

2. 알고리즘/기법

   • 연결 리스트 순회 (pointer 이동)
   • 포인터 재연결(pointer re-linking)

3. 핵심 키워드

   • 포인터(pointer)
   • 노드 삽입(node insertion)
   • 참조(reference)

---

풀이 아이디어

1. 문제 분해

• 주어진 llist(head node)로부터 시작해 position - 1번째 노드까지 순회한다.
• 새로운 노드를 생성하여, 현재 노드(current)와 다음 노드(current.next) 사이에 연결한다.

2. 핵심 로직 흐름

   current = head
   while (현재 위치 < 삽입 위치):
       current = current.next
   newNode.next = current.next
   current.next = newNode
   return head

3. 예외 처리

   • 삽입 위치가 0인 경우 → 새 노드를 head로 설정해야 하지만
     문제에서 position ≥ 1만 주어진다고 가정

---

코드

public static SinglyLinkedListNode insertNodeAtPosition(SinglyLinkedListNode llist, int data, int position) {
    SinglyLinkedListNode current = llist;
    SinglyLinkedListNode newItem = new SinglyLinkedListNode(data);
    
    int currentPosition = 1;
    while (currentPosition < position) {
        current = current.next;
        currentPosition++;
    }
    
    newItem.next = current.next;
    current.next = newItem;
    return llist;
}

---

시간·공간 복잡도

• 시간 복잡도: O(N) — 삽입 위치까지 순회 필요
• 공간 복잡도: O(1) — 추가 메모리는 새 노드 1개뿐

---

어려웠던 점

• llist를 순회하면서 포인터가 옮겨지는 과정을 정확히 이해하는 데 시간이 걸렸다.
• 연결 리스트는 값 교체가 아닌 포인터 연결 구조라는 점을 명확히 인식해야 했다.
  즉, “값을 밀어내는 것”이 아니라 참조를 바꾸는 작업임을 깨달았다.
  -> 따라서 일반 list처럼 값을 컨트롤하는게 아니라는 것을 다시 한번 실습하며 알 수 있었다.

---

배운 점 및 팁

• 연결 리스트 조작은 포인터 이동과 연결 구조 이해가 핵심이다.
• 새 노드를 삽입할 때, 다음 노드 연결(newItem.next = current.next) → 현재 노드 연결(current.next = newItem) 순서를 지켜야 한다.
• head 노드를 바꾸는 경우(삽입 위치 0)는 별도 조건문으로 처리 필요.

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/challenges/insert-a-node-at-a-specific-position-in-a-linked-list/problem
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • Insert a node at the head of a linked list

• 확장 문제 (GPT 추천):

  • 연결 리스트에서 특정 값 삭제(Delete a Node at a Specific Position)
  • Linked List의 중간 노드 찾기 (Find Middle Element)