코팅 테스트를 풀다 보니 ListNode가 나오기 시작했다. 처음 풀어보기에 고생을 좀 하여 정리를 좀 하려고 한다!!
🪼 왜 ListNode를 다뤄야 할까?
자주 보이는 자료구조 중 하나인 연결 리스트(Linked List) 는 알고리즘 문제에도 자주 등장하는 구조이다. 이 연결 리스트의 개념과 함께 ListNode라는 클래스를 이해하면 문제를 쉽게 접근할 수 있다.
👉 내가 현재 풀고 있는 LeetCode에서 ListNode 구조가 자주 나온다고 한다. 그렇기에 단순한 연결 리스트 개념만 알지 말고, 직접 포인터를 다루는 경험이 필요한 거 같다!
📌 연결 리스트란?
데이터와 포인터로 이루어진 일련의 노드
(Node)들이 순차적으로 연결된 자료구조
각 노드는 두 가지 정보를 가지고 있다
1. 실제 데이터 값
2. 다음 노드를 가리키는 포인터(next)
이렇게 각 노드가 다음 노드를 가리키면서 리스트처럼 동작하는 자료구조이다.
메모리에 연속적으로 저장되지 않아도 되기 때문에 유연하게 노드를 추가하거나 제거할 수 있다.
📌 연결 리스트의 종류
연결 리스트는 구조에 따라 여러 가지로 나뉜다
- 단일 연결 리스트 (Singly Linked List)
- 한 방향으로만 연결됨
- 위에서 설명한
ListNode구조
- 이중 연결 리스트 (Doubly Linked List)
- 앞 뒤 노드를 모두 가리킬 수 있는 구조
public class DoublyListNode{
int val;
DoublyListNode prev;
DoublyListNode next;
public DoublyListNode(int val){
this.val = val;
}
}- 원형 연결 리스트 (Circular Linked List)
- 마지만 노드의
next가 다시 첫 번째 노드를 가리킴
📌 배열 vs 연결 리스트
| 항목 | 배열 (Array) | 연결 리스트 (Linked List) |
|---|---|---|
| 메모리 저장 방식 | 연속된 공간 | 임의의 메모리 공간 |
| 접근 속도 | 빠름 (O(1)) | 느림 (O(n)) |
| 삽입/삭제 | 느림 (복사 필요) | 빠름 (포인터만 조정) |
| 메모리 효율 | 미리 공간 확보 필요 | 필요 시마다 노드 생성 |
배열
- 인덱스를 통한 접근이 빠르고 직관적
- 크기 변경이 어렵고 중간 삽입/삭제에 불리
연결 리스트
- 삽입/삭제가 빠르고 유연
- 특정 위치 접근이 느림(순차 탐색 필요)
🪼 ListNode 구조
public class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
this.next = null;
}
}- 각 노드는 하나의 정수형 값을 저장하며
- 다음 노드를 가리키는 포인터
next를 가지고 있다
📌 예제
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
node1.next.next = node3;🪼 ListNode 문제 해결 팁!
📌 더미 노드 사용
개념: 실제 데이터와 무관한 가짜 노드를 리스트 앞에 하나 만들어서 head(시작점)을 고정시켜주는 기법이다
- 리스트의 시작점이 바뀌는 경우(ex: 첫 번째 노트 삭제, 새 노드 삽입 등)에서 유용
- 매번
head를 체크하지 않고 깔끔하게 코드 작성 가능
EX) 특정 값 제거(val == target)
public ListNode removeElements(ListNode head, int val){
ListNode dummy = new ListNode(0); //더미 노드 생성
dummy.next = head;
ListNode current = dummy;
while(current.next != null){
if(current.next.val == val){
current.next = current.next.next; //건너뛰기
} else {
current = current.next;
}
}
return dummy.next;
}- 더미 노드가 있어서 첫 노드를 삭제하더라도
dummy.next는 안전하게 다음 노드를 가리킨다
📌 투 포인터 (Two Pointer) 패턴
개념: 리스트를 순회하거나 조작할 때 두 개의 포인터를 동시에 움직여서 속도 차를 이용하거나 상대적인 위치를 조절하는 기법이다
EX) 중간 노드 찾기 (slow & fast)
public ListNode middleNode(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;fast는 두 칸씩,slow는 한 칸씩 이동fast가 끝에 도달하면,slow는 중간에 있다
EX) k번째 노드 제거 (끝에서부터)
public ListNode removeNthFromEnd(ListNode head, int n){
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
//fast 먼저 n+1 칸 이동
for (int i = 0; i <= n; i++){
fast = fast.next;
}
//fast, slow 같이 이동
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//제거
slow.next = slow.next.next;
return dummy.next;- 더미 노드 + 투 포인터
slow가 삭제해야 할 노드의 바로 이전 위치에 도착한다
📌 포인터 조작 시 주의할 점
- 현재 노드, 이전 노드, 다음 노드를 명확하게 구분해야 한다
- 포인터를 변경할 때는 순서가 중요하다! ✨ 변경 전에 미리 다음 노드를 저장해두자
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;