TIL 정리_47(Linked List)

 

retrieve : 헤더 다음 데이터를 n에 할당해서 n부터 출력하도록 하는 것

Test class
public class LinkedListNode {
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.retrieve
} //첫 번째 헤더도 삭제가능

 

 

LinkedList 중복값 삭제 예제

정렬되어있지 않은 링크드리스트에 중복되는 값을 제거

-> 별도의 버퍼를 사용하지 않고 제거

3 -> 2 -> 1 -> 2 -> 4

버퍼를 사용하는 경우 : Hashset 중복 x 순서x

space(공간복잡도) : O(n) time(시간복잡도) : O(n)

 

버퍼 대신 포인터를 사용하여 문제풀이

n과 r을 선언 -> 둘 다 첫 번째 노드를 가리킴

System.out.println(n.data) //이전 코드 그대로 사용
void removeDups() {
Node n = header;
while (n.next != null) {
Node r = n;
while(r.next != null) { 코드 추가 while(n != null && r.next != null)
if(n.data == r.next.data) { //r은 n과 같은 위치에서 다음 노드로 이동
r.next = r.next.next;
} else {
r = r.next;
}
}
n = next;
}
}
}

public class RemoveDups {
public static void main (String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(3);
ll.append(2);
ll.append(2);
ll.retrieve();
ll.removeDups();
ll.retrieve();

**마지막 노드는 null 이기 때문에 지워지면 안된다

 

시간과 공간복잡도

시간 : O(n^2) 공간 : 고정된 포인터만 사용 O(1)

-> 버퍼와 비교하여 시간은 많이들지만 공간은 더 효율성있다

 

 

 

단방향 linkedList의 끝에서 k번째 노드를 찾는 알고리즘 구현

2 -> 3 -> 1 -> 4

 

방법 1

링크드리스트의 첫 번째 노드부터 순서대로 찾는다

public class Test {
public static void main (String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.retrieve();
int k = 2;
Node kth = kthTolast(first, k);
sysout(“Last k(” + k + “)th data is” + kth.data);
}
private static Node KthToLast(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;

 

 

방법2 (문제의 의도) 재귀호출 : 조건을 만족할때까지 자신을 호출

public class Test {
public static void main (String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.retrieve();
int k = 1; //뒤에서 몇 번째 값인지 할당
kthToLast(ll.getFirst(), k);
}
private static int KthToLast(Node n, int k) {
if (n == null) {
return 0;
}
int count = KthToLast(n.next, k) +1;
if(count == k) {
sysout(K + “th to last node is” + n.data);
}

-> 노드를 찾아야 함

자바에서는 한 개의 데이터만 반환 가능 -> 어떻게 노드를 반환할것인가?

 

 

객체 안에 count를 넣어서 객체의 주소를 반환

public class Test {
public static void main (String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.retrieve();
int k = 3
Reference r = new Reference();
Node found = kthToLast(ll.getFirst(), k, r);
System.out.println(found.data);
}

private static int KthToLast(Node n, int k, Reference r) {
if (n == null) {
return null;
}
Node found = KthToLast(n.next, k, r);
r.count++;
if(r.count == k) {
return n;
}
return found;
}
}

-> 공간 복잡도 O(n) 시간복잡도 O(n)

 

방법3 포인터를 이용

priavate static Node KthToLast(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(p != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}

-> 시간 O(n) 공간 O(1)