자료구조 - 단일 연결리스트(Linked List)

단일연결리스트 

- 모든 원소가 데이터, 링크 쌍으로 이루어져있고 이 링크를 통해 자신의 후속 원소와 연결되는 구조를 말한다.

- 앞서말했듯이 연결구조는 원소의 삽입과 삭제가 용이하다

(미리 지정된 연속된 주소공간으로 리스트가 표현되는 것이 아닌 각각의 원소가 다음 원소의 주소를 가지고 있기 때문에 

 삽입시에 공간을 늘리지 않아도 되기 때문이다.)

1. 삽입

a) 제잎 앞에 원소 삽입

1. 새로운 노드의 링크를 헤더의 다음 노드를 가리키도록 한다.

2. Header의 링크를 새로운 노드를 가리키게 한다.

*1 , 2번의 순서가 뒤바뀌면 Header의 다음노드를 가리키는 링크가 사라지기 때문에 1, 2번의 순서를 꼭 지켜야한다.

다음그림은 연결구조에서 맨앞에 원소의 삽입을 나타낸 그림이다

public void addFirst(int data) {
    Node newNode = new Node(data);
        
    //head가 null이면 리스트가 비어있는것이므로 head가 newNode를 가리키도록 한다 
    if(head == null) {
        head = newNode;
        return;
    }
        
    //새로운 노드의 링크를 head를 가리키게한다
    newNode.next = head;
    //헤드에 새노드를 담는다
    head = newNode;
}

a) 제일 앞에 원소 삭제

원소의 삭제 역시 간단하다

1. 삭제하고자 하는 원소의 바로 이전 원소를 찾는다 (삭제하고자 하는 원소를 가리키는 원소)

2. 삭제하고자 하는 원소의 이전 원소의 링크를 삭제하고자 하는 원소가 가리키는 원소를 가리키도록 바꾼다

3. 삭제하고자 하는 원소를 가리키는 링크가 없기 때문에 자연스레 쓰레기가 되어 처리된다.

public Node removeFirst() {
    //제거될 노드를 removed변수에 담는다 
    Node removed = head;
    //헤드가 현재 가리키는 노드의 다음 노드를 가리키게한다. 
    head = head.next;
    //제거될 노드를 리턴시켜준다.
    return removed;
}

b) 제일 뒤에 원소 삭제

1. 임시포인터에 head를 담는다

2. 임시포인터에 마지막 노드의 이전노드를 담는다

3. 마지막 이전노드의 링크를 null로 한다

*주의할점 : 임시포인터에 마지막노드를 담고 null로 한다면 임시노드에 담긴 것을 없앨뿐

    원래의 리스트에서 마지막노드에 대한 링크가 제거되는 것이 아니다.

*코드

public void removeLast() {
    Node temp = head;
    
    //임시 노드에 마지막 이전 노드를 담는다
    while(temp.next.next != null)
        temp = temp.next;
    //마지막 이전노드의 링크를 null로 한다
    temp.next = null;
}

c) 원하는 노드 삭제

1. 예를들어 리스트 상에 1,2,3 노드가 존재하고 2라는 중간 노드를 제거한다고 하자

2. 지우려는 노드가 리스트상에 존재하는지 확인한다, 없다면 종료하고 있다면 진행한다

3. 2노드의 전노드인 1을 찾아 1의 next의 주소를 2노드의 next의 주소값으로 한다

*코드

public void removeNode(int removeData) {
        //지우려는 데이터가 존재 하지 않으면 종료
        if(findNode(removeData) == null)
            return;
        
        //지워질 노드 바로 전노드
        Node removeBefore = this.head;
        
        while(removeBefore.next.data != removeData && removeBefore != null)
            removeBefore = removeBefore.next;
        
        //지워질 노드
        Node removeNode = removeBefore.next;
        
        removeBefore.next = removeNode.next;        
    }

*전체 코드

public class LinkedList {
    private Node head;
    
    public void addFirst(int data) {
        Node newNode = new Node(data);
        
        //head가 null이면 리스트가 비어있는것이므로 head가 newNode를 가리키도록 한다 
        if(head == null) {
            head = newNode;
            return;
        }
        
        //새로운 노드의 링크를 head를 가리키게한다
        newNode.next = head;
        //헤드에 새노드를 담는다
        head = newNode;
    }
    
    public void addLast(int data) {
        Node newNode = new Node(data);
        
        //head가 null이면 리스트가 비어있는것이므로 head가 newNode를 가리키도록 한다 
        if(head == null) {
            head = newNode;
            return;
        }
        //임시 포인터에 head를 담는다
        Node temp = head;
        /**맨마지막 원소까지 이동한다 temp.next가 null인지 
        비교를해야 임시 포인터가 null되는것을 막을 수 있다.*/
        while(temp.next != null)
            temp = temp.next;
        //맨마지막 원소의 링크에 새로운 노드를 담는다
        temp.next = newNode;
    }
    
    public Node removeFirst() {
        //제거될 노드를 removed변수에 담는다 
        //(지역변수로 스택에 담기므로 메소드가 끝나면 사라지는 변수이기 때문에 garbage collector에 의해 수집된다)
        Node removed = head;
        //헤드가 현재 가리키는 노드의 다음 노드를 가리키게한다. 
        head = head.next;
        //제거될 노드를 리턴시켜준다.
        return removed;
    }
    
    public void removeLast() {
        Node temp = head;
        
        //임시 노드에 마지막 이전 노드를 담는다
        while(temp.next.next != null)
            temp = temp.next;
        //마지막 이전노드의 링크를 null로 한다
        temp.next = null;
    }
    
    public Node findNode(int findData) {
        Node findNode = this.head;
        
        while(findNode.data != findData && findNode != null) 
            findNode = findNode.next;        
        
        return findNode;
    }
    
    public void removeNode(int removeData) {
        //지우려는 데이터가 존재 하지 않으면 종료
        if(findNode(removeData) == null)
            return;
        
        //지워질 노드 바로 전노드
        Node removeBefore = this.head;
        
        while(removeBefore.next.data != removeData && removeBefore != null)
            removeBefore = removeBefore.next;
        
        //지워질 노드
        Node removeNode = removeBefore.next;
        
        removeBefore.next = removeNode.next;        
    }
    
    public void printList() {
        Node temp = head;        
        while(temp != null) {
            System.out.print(temp.data);
            if(temp.next != null)
                System.out.print(" -> ");
            temp = temp.next;
        }
    }
    
    class Node{
        private Node next;
        private int data;
        
        public Node(int data) {
            this.data = data;
        }
    }    
 
}