[자료구조] Linked List

Linked List 개념

• 컴퓨터에 자료를 저장하는 구조의 한 종류
• 일렬로 연결된 데이터를 저장할 때 사용된다
• linked list는 길이가 정해져 있지 않는 데이터의 연결된 집합이다
• 데이터를 저장할 수 있는 공간이 있으면 그 안에 다음 데이터의 주소를 가지고 있는 구조
• 링크드 리스트는 데이터를 중간에 삽입이 쉽다.
• 배열보다 속도는 느리다.

배열

• 배열 방의 크기를 한번 정하면 늘리거나 줄일 수가 없다.

Linked List 단/양 방향

• 단방향 Linked List: 한 방향으로만 이동할 수 있는 Linked List
• 양방향 Linked List: 다음 노드의 주소를 가지고 있고 내 앞 노드의 주소도 추가로 가지고 있어서 앞 뒤로 자유롭게 다닐 수 있다.

단반향 Linked List

# 단방향 Linked List 구현
class Node{
	int data;
    Node next = null;
    
    Node(int data){
    	this.data = data
    }
    
    void append(int data){
    	Node end = new Node(data);
        Node n = this;
        while(n.next != null){
        	n = n.next;
        }
        n.next = end;
    }
    
    void delete(int data){
    	Node n = this;
        while(n.next != null){
        	if(n.next.data == data){
            	n.next = n.next.next;
            }
            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 head = new Node(1);
        head.append(2);
        head.append(3);
        head.append(4);
        head.retrieve();
    }
}
# 결과 값
1 -> 2 -> 3 -> 4

public class SinglyLinkedList{
	public static void main(String[] args){
    	Node head = new Node(1);
        head.append(2);
        head.append(3);
        head.append(4);
        head.retrieve();
        head.delete(2);
        head.delete(3);
        head.retrieve();
    }
}
# 결과 값
1 -> 2 -> 3 -> 4
1 -> 4

Node 클래스를 감싸는 Linked List 클래스

• 위의 Node 클래스는 살짝 취약하다 -> Header가 리스트의 첫 번째 값이면서 대표이기 때문에 어떤 프로세스가 이 Header 값이 더 이상 필요가 없어져서 삭제해 버리면 어떤 오브젝트가 아직 이 헤더에 포인터를 가지고 있는 경우 문제가 생긴다.
• 이런 문제 해결을 위해 Node 클래스를 Linked List라는 클래스로 감싸서 Linked List의 헤더를 데이터가 아니 Linked List의 시작을 알려주는 용도로만 쓰도록 저장을 한다. 그리고 그 안에 Node클래스를 만든다.

# Node 클래스를 감싸는 Linked List 클래스 구현
class LinkedList{
	Node header;
    
    static class Node{
    	int data;
        Node next = null;
    }
    
    LinkedList(){
		header = new Node();
	}
    
    void append(int data){
    	Node end = new Node();
        end.data = d;
        Node n = header;
        while(n.next != null){
        	n = n.next;
        }
        n.next = end;
    }
    
    void delete(int data){
    	Node n = header;
        while(n.next != null){
        	if(n.next.data == data){
            	n.next = n.next.next;
            }
            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 LinkedListNode {
	public static void main(String[] args){
    	LinkedList ll = new LinkedList();
        ll.append(1);
        ll.append(1);
        ll.append(1);
        ll.append(1);
        ll.retrieve();
        ll.delete(1);
        ll.retrieve();
    }
}
# 결과값
1 -> 2 -> 3 -> 4
2 -> 3 -> 4

Linked List 중복값 삭제

• 정렬되어 있지 않은 Linked List의 중복값 제거(단, 버퍼를 사용하지 않음)
  Ex) 3 -> 2 -> 1 -> 2 -> 4

class LinkedList{
	Node header;
    
    static class Node{
    	int data;
        Node next = null;
    }
    
    LinkedList(){
		header = new Node();
	}
    
    void append(int data){
    	Node end = new Node();
        end.data = d;
        Node n = header;
        while(n.next != null){
        	n = n.next;
        }
        n.next = end;
    }
    
    void delete(int data){
    	Node n = header;
        while(n.next != null){
        	if(n.next.data == data){
            	n.next = n.next.next;
            }
            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);
    }    
    
    # Linked List 중복값 삭제함수 구현
    void removeDups(){
    	Node n = header;
        while(n != null && n.next != null){
        	Node r = n;
            while(r.next != null){
            	if(n.data == r.next.data){
                	r.next = r.next.next
                } 
                else{
                	r = r.next;
                }
            }
            n.next;
        }
    }
}

# 테스트 클래스
public class RemoveDups {
	public static void main(String[] args)[
    	LinkdeList ll = new LinkedList();
        ll.append(1);
        ll.append(3);
        ll.append(2);
        ll.append(2);
        ll.append(4);
        ll.retrieve();
        ll.removeDups();
        ll.retrieve();
    }
}
# 결과 값
1 -> 3 -> 2 -> 2 -> 4
1 -> 3 -> 2 -> 4

단방향 Linked List 뒤부터 세기

# 방법 1 
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. 재귀호출
class Reference{
	public int count;
}

Node 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;
}

# 방법 3. 포인터
Node kthToLast(Node fist, 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;
}