Set - LinkedHashSet 이론과 구현

 

📌 LinkedHashSet<E>

- Set<E> 인터페이스를 구현한 클래스이자, HashSet<E>의 자식 클래스

- 수집한 원소를 집합 형태로 관리하여 저장공간(capacity)을 동적관리

- 중복 불가

- 입력 순서와 출력 순서는 동일하다. (HashSet과 차이점)

 

 

---

 

📌 Set<E>  주요 메서드

구분	리턴타입	메서드 이름	기능
데이터 추가	boolean	add(E element)	매개변수로 입력된 원소를 리스트에 추가
	boolean	addAll(Collection <? Extends E> c	매개변수로 입력된 컬렉션 전체를 추가
데이터 삭제	boolean	remove<Object o)	원소 중 매개변수입력과 동일한 객체 삭제
	void	clear()	전체 원소 삭제
데이터 정보추출	boolean	isEmpty()	Set 객체가 비워져있는지 여부 리턴
	boolean	contains(Object o)	매개변수로 입력된 원소가 있는지 여부를 리턴
	int	size()	리스트 객체 내에 포함된 원소의 개수
	iterator<E>	iterator()	Set 객체내의 데이터를 연속하려 꺼내는 Iterator 객체 리턴
Set 객체 배열 반환	Object[]	toArray()	리스트를 Object 배열로 변환
	T[]	toArray(T[] t)	입력매개변수로 전달한 타입의 배열로 변환

 

 

---

📌 LinkedHashSet<E>

- 입력과 출력의 순서가 동일

 

예시코드)

public class LinkedHashSetMethod {
    public static void main(String[] args) {
        Set<String> linkedSet1 = new LinkedHashSet<>();

        //#1. add(E element)
        linkedSet1.add("가");
        linkedSet1.add("나");
        linkedSet1.add("가");
        System.out.println(linkedSet1.toString()); //[가, 나]

        //#2. addAll(다른 set 객체)
        Set<String> linkedSet2 = new LinkedHashSet<>();
        linkedSet2.add("나");
        linkedSet2.add("다");
        linkedSet2.addAll(linkedSet1);
        System.out.println(linkedSet2.toString()); //[나, 다, 가] 입력 순서대로 출력

        //#3. remove(Object o)
        linkedSet2.remove("나");
        System.out.println(linkedSet2.toString()); //[다, 가]

        //#4. clear
        linkedSet2.clear();
        System.out.println(linkedSet2.toString());

        //#5. isEmpty
        System.out.println(linkedSet2.isEmpty()); //true

        //#6. contains (Object o)
        Set<String> linkedSet3 = new LinkedHashSet<>();
        linkedSet3.add("가");
        linkedSet3.add("나");
        linkedSet3.add("다");
        System.out.println(linkedSet3.contains("나")); //true
        System.out.println(linkedSet3.contains("라")); //false

        //#7. size
        System.out.println(linkedSet3.size()); //3

        //#8. iterator
        Iterator<String> iterator = linkedSet3.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //#9 toArray : 배열로 바꾸기
        Object[] objArray = linkedSet3.toArray();
        System.out.println(Arrays.toString(objArray));

        //#10. toArray(T[] t)
        String[] strArray1 = linkedSet3.toArray(new String[0]); //컴파일러가 알아서 저장공간을 늘려준다.
        System.out.println(Arrays.toString(strArray1)); //[가, 나, 다]

        String[] strArray2 = linkedSet3.toArray(new String[5]);
        System.out.println(Arrays.toString(strArray2)); //[가, 나, 다, null, null]
    }
}

 

 

---

 

💡 LinkedHashSet 구현

- LinkedHashSet을 다음과 같이 구현해보았다.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class MyLinkedHashSet<E> {
    private final Map<E, Node<E>> map;
    private Node<E> head;
    private Node<E> tail;

    private static class Node<E> {
        E value;
        Node<E> next;
        Node<E> prev;

        Node(E value){
            this.value = value;
        }
    }

    public MyLinkedHashSet(){
        map = new HashMap<>();
        head = null;
        tail = null;
    }

    public boolean add(E element){
        if(map.containsKey(element)){
            return false;
        }
        Node<E> newNode = new Node<>(element);
        map.put(element, newNode);

        if(tail == null){
            head = newNode;
            tail = newNode;
        }else{
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        return true;
    }

    public boolean remove(E element){
        Node<E> node = map.remove(element);
        if(node == null){
            return false; //element not found
        }

        if(node.prev != null){
            node.prev.next = node.next;
        }else{
            head = node.next;
        }

        if(node.next != null){
            node.next.prev = node.prev;
        }else{
            tail = node.prev;
        }
        return true;

    }

    public boolean contains(E element){
        return map.containsKey(element);
    }

    public int size(){
        return map.size();
    }

    //입출력 순서 동일
    public void printElements(){
        Node<E> current = head;
        while(current != null){
            System.out.println(current.value);
            current = current.next;
        }
        System.out.println();
    }

    public void clear(){
        map.clear();
        head = null;
        tail = null;
    }

    public  Iterator<E> iterator(){
        return new CustomIterator();
    }

    private class CustomIterator implements Iterator<E> {
        private Node<E> currentNode = head;

        @Override
        public boolean hasNext() {
            return currentNode != null;
        }

        @Override
        public E next() {
            if(!hasNext()){
                throw new NoSuchElementException();
            }
            E value = currentNode.value;
            currentNode = currentNode.next;
            return value;
        }
    }

}

 

 

---

필드 및 생성자

 

- Map을 사용하려 값과 해당 노드를 앞뒤 노드와 연결한다.

- head : 첫번째 노드를 가리키는 포인터

- tail : 마지막 노드를 가리키는 포인터

- Node<E> 클래스 : 노드의 값, 앞 뒤 정보를 저장

- value : 노드가 저장하는 값

- next : 다음 노드를 가리키는 포인터

- prev : 이전 노드를 가리키는 포인터

private final Map<E, Node<E>> map;
private Node<E> head;
private Node<E> tail;

private static class Node<E> {
    E value;
    Node<E> next;
    Node<E> prev;

    Node(E value){
        this.value = value;
    }
}

public MyLinkedHashSet(){
    map = new HashMap<>();
    head = null;
    tail = null;
}

 

 

---

 

요소 추가 (add)

 

- 이미 집합에 존재하는 값이 있다면 추가하지 않는다.

- 새로운 노드를 생성하여, map에 value와 해당 노드를 추가한다.

public boolean add(E element){
    if(map.containsKey(element)){
        return false;
    }
    Node<E> newNode = new Node<>(element);
    map.put(element, newNode);

    if(tail == null){// 첫 번째 요소일 경우
        head = newNode; // head와 tail 모두 새 노드를 가리킴
        tail = newNode;
    }else{// 그 외의 경우
        tail.next = newNode;// tail의 next를 새 노드로 설정
        newNode.prev = tail;// 새 노드의 prev를 현재 tail로 설정
        tail = newNode;// tail을 새 노드로 갱신
    }
    return true;
}

 

 

---

 

요소 삭제 (remove)

 

- Map에서 value에 해당하는 노드를 제서한다.

- 값이 존재하지 않으면 false 반환

public boolean remove(E element){
    Node<E> node = map.remove(element);
    if(node == null){
        return false; //element not found
    }

    if(node.prev != null){ // node가 첫 번째 노드가 아니라면
        node.prev.next = node.next; // 이전 노드가 다음 노드를 가리키도록 수정
    }else{ // 첫 번째 노드를 제거할 경우
        head = node.next; // head를 node의 다음 노드로 갱신
    }

    if(node.next != null){ // node가 마지막 노드가 아니라면
        node.next.prev = node.prev; // 다음 노드가 이전 노드를 가리키도록 수정
    }else{ // 마지막 노드를 제거할 경우
        tail = node.prev; // tail을 node의 이전 노드로 갱신
    }
    return true;

}

 

 

---

 

 

값이 존재하는지 확인 (contains)

 

- Map에 해당 값이 존재하는지 확인한다.

 public boolean contains(E element){
    return map.containsKey(element);
}

 

 

---

 

집합 크기 반환 (size)

 

- Map의 size를 반환한다.

public int size(){
    return map.size();
}

 

 

---

 

집합의 요소를 삽입 순서대로 출력

 

- LinkedHashSet의 특징인 집합의 요소를 삽입 순서대로 출력하기 위해서, head부터 포인터를 옮겨가며 출력한다.

public void printElements(){
    Node<E> current = head;
    while(current != null){
        System.out.println(current.value);
        current = current.next;
    }
    System.out.println();
}

 

 

---

 

모든 요소 제거 clear()

 

- Map의 모든 요소를 제거한다.

- 이때 head와 tail도 null로 초기화한다.

public void clear(){
    map.clear();
    head = null;
    tail = null;
}

 

 

---

 

Iterator 구현

 

- Iterator 인터페이스를 구현하여 Iterator를 구현한다.

 public  Iterator<E> iterator(){
    return new CustomIterator(); // Iterator를 반환
}

private class CustomIterator implements Iterator<E> {
    private Node<E> currentNode = head; // 현재 노드를 head로 초기화

    @Override
    public boolean hasNext() {
        return currentNode != null; // currentNode가 null이 아니면 더 많은 요소가 있음
    }

    @Override
    public E next() {
        if(!hasNext()){
            throw new NoSuchElementException(); // 더 이상 요소가 없다면 예외발생
        }
        E value = currentNode.value; // 현재 노드의 값을 반환
        currentNode = currentNode.next; // 다음 노드로 이동
        return value;
    }
}