메모
02 연결리스트
- 차례로 연결된 노드를 표현해주는 자료구조임.
- 연결리스트는 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없음.
- 연결리스트의 장점은 시작 지점에 아이템을 추가하거나, 삭제하는 연산을 상수 시간에 할 수 있음.
연결리스트 만들기
class Node {
Node next = null;
int data;
public Node(int d) {
data = d;
}
void appendToTail(int d) {
Node end = new Node(d);
Node n = this;
while (n.next != null) {
n = n.next;
}
n.next = end;
}
}
- 이 코드는 LinkedList 자료구조를 사용하지 않음.
- 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용함.
- 이런식의 구현은 조심해야 함.
- 여러 객체들이 동시에 연결리스트를 참조하는 도중, head 가 바뀌면 어떻게 해야할지 생각해야 함.
- head 가 바뀌었음에도 어떤 객체는 이전 head 를 계속 가리키고 있을 수도 있음.
- 할 수 있다면 Node 클래스를 포함하는 LinkedList 클래스를 만드는 게 좋음.
- 해당 클래스 안에 head Node 변수를 단 하나만 정의해 놓으면 위 문제를 해결할 수 있음.
- 면접에서 연결리스트에 대해 이야기할 때 단방향 인지 양방향인지에 대해 반드시 인지해야 함.
단방향 연결리스트에서 노드 삭제
Node deleteNode(Node head, int d) {
Node n = head;
if (n.data == d) {
return head.next; /* head를 움직인다. */
}
while (n.next != null) {
if (n.next.data == d) {
n.next = n.next.next;
return head; /* head는 변하지 않는다. */
}
n = n.next;
}
return head;
}
- 노드 삭제 시, 널 포인터 검사를 반드시 해야 함.
- 필요하면 head 와 tail 포인터도 갱신해야 함
- C, C++ 처럼 메모리 관리가 필요한 언어의 경우, 삭제한 노드에 할당되었던 메모리가 제대로 반환되었는지 반드시 확인해야 함.
Runner 기법
- 부가 포인터라고도 함.
- 연결리스트 문제에서 많이 활용되는 기법임.
- 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것임.
- 이때, 한 포인터가 다른 포인터보다 앞서도록 함.
- ex) 앞선 포인터가 따라오는 포인터보다 항상 지전된 개수만큼을 앞서도록 할 수 있음.
- ex) 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있음.
재귀 문제
- 연결리스트 관련 문제는 상당수 재귀 호출에 의존함.
- 연결리스트 문제를 푸는 데 어려움이 있다면 재귀적 접근법을 확인해봐야 함.
- 재귀 호출 깊이가 n일 경우 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용하게 됨.
* 코드 라이브러리
HashMapList<T, E>
- HashMap<T, ArrayList> 를 줄여쓴 것임.
- T 타입의 원소에서 E 타입의 ArrayList 로의 대응을 나타냄.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
public class HashMapList<T, E> {
private HashMap<T, ArrayList<E>> map = new HashMap<T, ArrayList<E>>();
/* Insert item into list at key. */
public void put(T key, E item) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<E>());
}
map.get(key).add(item);
}
/* Insert list of items at key. */
public void put(T key, ArrayList<E> items) {
map.put(key, items);
}
/* Get list of items at key. */
public ArrayList<E> get(T key) {
return map.get(key);
}
/* Check if hashmaplist contains key. */
public boolean containsKey(T key) {
return map.containsKey(key);
}
/* Check if list at key contains value. */
public boolean containsKeyValue(T key, E value) {
ArrayList<E> list = get(key);
if (list == null) return false;
return list.contains(value);
}
/* Get the list of keys. */
public Set<T> keySet() {
return map.keySet();
}
@Override
public String toString() {
return map.toString();
}
}
LinkedListNode(연결리스트)
public class LinkedListNode {
public LinkedListNode next;
public LinkedListNode prev;
public LinkedListNode last;
public int data;
public LinkedListNode(int d, LinkedListNode n, LinkedListNode p) {
data = d;
setNext(n);
setPrevious(p);
}
public LinkedListNode(int d) {
data = d;
}
public LinkedListNode() { }
public void setNext(LinkedListNode n) {
next = n;
if (this == last) {
last = n;
}
if (n != null && n.prev != this) {
n.setPrevious(this);
}
}
public void setPrevious(LinkedListNode p) {
prev = p;
if (p != null && p.next != this) {
p.setNext(this);
}
}
public String printForward() {
if (next != null) {
return data + "->" + next.printForward();
} else {
return ((Integer) data).toString();
}
}
public LinkedListNode clone() {
LinkedListNode next2 = null;
if (next != null) {
next2 = next.clone();
}
LinkedListNode head2 = new LinkedListNode(data, next2, null);
return head2;
}
}
- 종종 연결리스트 내부에 접근해야 할 필요가 있기에 내부적으로 제공되는 연결리스트 클래스만으로 부족함이 있음.
- 메서드와 변수에 접근해야 할 일이 종종 발생하기에 public 으로 선언함.
면접 문제
2.1 중복 없애기
- 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.
- 힌트
- 해시테이블을 생각해 보았나? 연결리스트를 한 번만 읽어서 해결할 수 있어야 한다.
- 추가 공간 없이 O(N^2) 시간에 할 수 있을 것이다. 포인터 두 개를 사용해 보라. 두 번째 포인터는 첫 번째 포인터 앞에서 검색을 해나갈 것이다.
- 연관 문제
- 임시 버퍼를 사용할 수 없다면 어떻게 풀 수 있을까?
2.2 뒤에서 k번째 원소 구하기
- 단방향 연결리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라.
- 힌트
- 연결리스트의 크기를 알고 있으면 어떠한가? 마지막에서 K번째 원소를 찾는 것과 X번째 원소를 찾는 것의 다른 점은 무엇인가?
- 연결리스트의 크기를 모른다면, 계산해서 알아낼 수 있는가? 이 방법이 수행 시간에 어떤 영향을 끼치는가?
- 재귀로 구현해 보라. 마지막에서 (K - 1)번째 원소를 찾을 수 있다면, K번째 원소도 찾을 수 있겠는가?
- 값을 여러 개 반환하는 것이 유용할 수도 있다. 어떤 언어에서는 값을 여러개 반환할 수 없지만, 이를 해결하는 방법은 모든 언어에서 다 제공한다. 해결 방법에는 무엇이 있을까?
- 순환적 방법으로 할 수 있는가? 두 포인터가 인접한 노드를 가리키고 있고 같은 속도로 연결리스트를 순회한다고 가정해 보자. 포인터 하나가 연결리스트의 끝에 도달했을 때 다른 하나는 어디에 있겠는가?