linked list 구현
먼저 아주 간단한 linked list를 구현해보겠다.
class Node {
private int data;
private Node next = null;
public Node(int d) {
this.data = d;
}
void append(int d) {
Node n = this;
Node end = new Node(d);
while(n.next != null) {
n = n.next;
}
n.next = end;
}
void delete(int d) {
Node n = this;
while(n.next != null) {
if(n.next.data == d) {
n.next = n.next.next;
break;
} else {
n = n.next;
}
}
}
void retrieve() {
Node n = this;
while(n.next != null) {
System.out.print(n.data + " -> ");
n = n.next;
}
System.out.println(n.data);
}
}
public class SinglyLinkedList {
public static void main(String[] args) {
Node node = new Node(1);
node.append(2);
node.append(3);
node.append(4);
node.retrieve();
node.delete(2);
node.delete(3);
node.retrieve();
node.delete(1);
node.retrieve();
}
} 이 코드는 Node라는 클래스로 linked list 간단하게 구현해 보았다. 추가, 삭제 그리고 저장된 모든 값들을 출력하는 메소드만 만들었다. 추가와 삭제가 제대로 되는거 같지만 Node를 만들 때 값을 넣으므로 Header에 값이 들어간 상태로 만들어져 첫번째 값은 삭제가 안된다는 것.
class LinkedList {
Node header;
static class Node{
private int data;
private Node next = null;
}
LinkedList() {
header = new Node();
}
void append(int d) {
Node end = new Node();
end.data = d;
Node n = header;
while(n.next != null) {
n = n.next;
}
n.next = end;
}
void delete(int d) {
Node n = header;
while(n.next != null) {
if(n.next.data == d) {
n.next = n.next.next;
break;
} else {
n = n.next;
}
}
}
void retrieve() {
Node n = header.next;
while(n.next != null) {
System.out.print(n.data + " -> ");
n = n.next;
}
System.out.println(n.data);
}
}
public class SinglyLinkedList {
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.retrieve();
ll.delete(1);
ll.delete(3);
ll.retrieve();
}
}위 코드는 이전에 만들었던 단점을 보완한 코드이다 Header를 선언함으로써 Linked List 생성시 값을 넣지 않아도 된다. Header는 데이터를 담지않고 다음 node의 주소만 담고 있으므로 첫번째 값을 삭제 할 수 있게 되었다.
이제 간단한 알고리즘 문제를 풀어보도록 하겠다
문제1) 정렬 되어 있지 않은 linkedlist의 중복되는 값을 제거하시오.
방법 1. 별도의 버퍼를 만들어서
3 -> 2 -> 1 -> 2 -> 4
버퍼를 사용한다면?
HashSet을 선언하여 중복값을 제거 해보겠다.
linkedlist를 돌면서 hashset에 값을 저장한다.
공간을 O(n)을 사용함.
시간도 O(n)걸림.
방법 2. 버퍼를 사용하지 않고 해보자
포인터를 지칭하는 n , runner를 가르키는 r
n이 r에게 3이 있다면 지우고와라 linkedlist를 돌면서 3이 없으므로 n은 다음 값인 2에서 다시 2가 있다면 지우라고 한다. 그럼 2가 있으므로 2를 지우고 n은 그렇게 마지막 4까지 간다면 이 문제는 끝나게된다. 아래와 구현해 보았다.
void removeDuplicate() {
Node n = header;
while(n != null && n.next != null) {
Node r = n;
while(r.next != null) {
if(r.next.data == n.data) {
r.next = r.next.next;
} else {
r = r.next;
}
}
n = n.next;
}
}
이 경우 r이 n의 제곱만큼 움직이게 되므로
시간 복잡도는 O(n^2) 이고, 버퍼를 사용하지 않고 포인터를 사용했으므로 공간 복잡도는 O(1)이 된다.
문제2) 뒤에서 k번째 노드를 구하시오.
방법 1. 노드의 전체 개수에서 k의 값을 빼서 구하기
public static Node kthToLastNode(Node first, int k) {
Node n = first;
int total = 1;
// 전체 노드 갯수
while (n.next != null) {
total++;
n = n.next;
}
n = first;
for (int i = 1; i < total - k + 1; i++) {
n = n.next;
}
return n;
}전체 노드의 갯수를 구한 뒤 전체 노드의 값에서 k을 빼주고 1을 더하면 뒤에서 k번째의 노드를 구할 수 있다.
방법 2-1. 재귀함수 활용
public static int kthToLastNodeRecursion(Node n, int k) {
if(n == null) {
return 0;
}
int count = kthToLastNodeRecursion(n.next, k) + 1;
if(count == k ){
System.out.printf(
"(재귀) 뒤에서 %d번째 노드의 값은 : %d\n", k, n.data);
}
return count;
}linked list를 순회하여 노드가 null을 만나게 되면 0을 반환하고, count 변수에 1을 더하고 count 변수가 k와 같게 되면 현재 노드의 값을 출력해주는 재귀함수이다. 값은 나올지 몰라도 반환받는 타입이 int이므로 원하는 메서드가 아니다.
방법 2-2. 다른 객체를 파라미터에 넣어 재귀함수 만들기
static class Reference {
public int count;
}
public static Node kthToLastNodeRecursionGetNode(
Node n, int k, Reference r) {
if(n == null) {
return null;
}
Node found = kthToLastNodeRecursionGetNode(n.next, k, r);
r.count++;
if(r.count == k) {
return n;
}
return found;
}Reference 객체를 만들어 count 변수를 저장해주고 재귀함수에 Reference 객체를 매개변수로 넣어 Node를 구하는 메서드이다.
방법 3. 포인터를 활용
public static Node kthToLastNodeUsePointer(Node first , int k) {
Node p1 = first;
Node p2 = first;
for(int i = 0 ; i<k; i++) {
if(p1 == null) return null;
p1 = p1.next;
}
while(p1 != null ) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}메서드내에서 Node객체를 두개 만들어서 p1(runner) k만큼 뒤로 보내고, p1, p2 둘다 p1이 null이 될때까지 다음 노드가 된다. p1이 null이 된다면 p2는 뒤에서 k번째 노드가 되고 반환한다.
문제3) 단방향 Linked List 중간노드 삭제
단방향 Linked List의 중간노드를 삭제 하려면 어떻게 해야할까?
삭제하고자 하는 노드를 다음노드로 복제하면 된다. 삭제하고자 하는 노드가 2번 노드라면 다음 3번노드의 값을 복제하고 3번노드의 다음 노드 주소를 복제하면 2번노드는 없어지게 되는것이다. (편의상 노드가 네개이면 첫번째는 1번으로 함) 코드 구현은 다음과 같다.
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.retrieve();
deleteNode(ll.get(3));
ll.retrieve();
}
private static boolean deleteNode(Node node) {
if(node == null || node.next == null) {
return false;
}
Node next = node.next;
node.data = next.data;
node.next = next.next;
return true;
}참고) 중간노드의 삭제 이므로 마지막 노드는 삭제하지 못한다.
