[Linked List] 중복값 삭제

youtu.be/Ce4baygLMz0

 

package dataStructure.singlyLinkedList;

import java.util.HashSet;
import java.util.Iterator;

public class SinglyLinkedList {

    private Node head;

    public SinglyLinkedList() {
        head = new Node();
    }

    private static class Node{
        private int data;
        private Node next = null;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }
    }

    public boolean append(int d){
        try {
            Node end = new Node();
            end.data = d;

            Node nextNode = head;
            while (nextNode.next != null) {
                nextNode = nextNode.next;
            }

            nextNode.next = end;


            return true;

        }catch (Exception e){
            return false;
        }

    }

    public boolean delete (int d){
        try{

            Node nextNode = head;
            while(nextNode.next != null){
                if(nextNode.next.data == d){
                    nextNode.next = nextNode.next.next;
                }

                nextNode = nextNode.next;
            }

            return true;

        }catch (Exception e){
            return false;
        }
    }

    public void retrieve(){
        Node nextNode = head;
        if(nextNode.next != null){
            nextNode = nextNode.next;

            System.out.print(nextNode.data);
            while(nextNode.next != null){
                nextNode = nextNode.next;
                System.out.print(" -> " + nextNode.data);
            }
            System.out.println();
        }
    }

    public void removeDups(){

        /**
         * 버퍼 사용
         *
         * 시간 O(N)
         * 공간 O(N) ???
         * */
        HashSet hs = new HashSet<Integer>();
        Node nextNode = head;

        while(nextNode.next != null){
            nextNode = nextNode.next;
            hs.add(nextNode.data);
        }

        Iterator it = hs.iterator();
        nextNode = head;
        while(it.hasNext()){
            int d = (int) it.next();
            Node n = new Node(d);
            nextNode.next = n;
            nextNode = n;
        }

        /**
         * 버퍼 미사용
         *
         * 시간 O(N^2)
         * 공간 O(1)
         * */
        Node nextNode = head;
        while(nextNode.next != null){
            nextNode = nextNode.next;
            Node runner = nextNode;

            while(runner.next != null){
                if(nextNode.data == runner.next.data){
                    runner.next = runner.next.next;
                }else{
                    runner = runner.next;
                }
            }

        }
    }

}

 

package dataStructure.singlyLinkedList;

public class RemoveDups {

    public static void main(String[] args) {

        SinglyLinkedList ll = new SinglyLinkedList();

        ll.append(2);
        ll.append(1);
        ll.append(3);
        ll.append(6);
        ll.append(2);
        ll.append(2);

        ll.retrieve();

        ll.removeDups();

        ll.retrieve();

    }

}