자료구조 - List, Set, Stack, Queue

Jobmania·2023년 1월 25일

자료구조, 알고리즘(코딩테스트)

목록 보기

11/15

1. ArrayList, LinkedList

public class Timing {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        Long duration = timeOperation(linkedList);  // 실제 작업시간..

        System.out.println(duration);
    }

    private static Long timeOperation(List<Integer> arrayList) {
        long start = System.currentTimeMillis();

        for (int i = 0; i < 1000000; i++) { //399
            arrayList.add(0,i);
        }
        
        return System.currentTimeMillis() - start;
    }
}

ArrayList 실행결과

LinkedList 실행결과

2. HashSet, TreeSet, LinkedHashSet

HashSet

  public static void main(String[] args) {
        HashSet<String> strings = new HashSet<>();
        // set은 인덱스가 없으며, 중복 x, 순서가 없다..
        strings.add("무");
        strings.add("모");
        strings.add("모");
        strings.add("마");
        strings.add("망가");
        strings.add("망각");
        strings.add("혼돈");

        System.out.println(strings);
        System.out.println(strings.contains("망각"));
    }

중복 제거 용도, 순서를 보장 하진 않는다.

LinkedHashSet

    public static void main(String[] args) {
        // 순서 보장
        LinkedHashSet<String> strings = new LinkedHashSet<>();
        strings.add("무");
        strings.add("모");
        strings.add("모");
        strings.add("마");
        strings.add("망가");
        strings.add("망각");
        strings.add("혼돈");
        strings.add("혼돈");
        strings.add("강혼돈");
        strings.add("무");

        System.out.println(strings);
        System.out.println(strings.contains("망각"));

    }

중복 제거 및 입력 순서에 따른 순서를 보장함.

TreeSet

 public static void main(String[] args) {

        // 정렬 o
        TreeSet<Integer> list = new TreeSet<>();
        list.add(3);
        list.add(23);
        list.add(43);
        list.add(13);
        System.out.println(list);


        TreeSet<String> strings = new TreeSet<>();
        strings.add("abc");
        strings.add("aaa");
        strings.add("aaa");
        strings.add("baa");
        strings.add("caa");
        strings.add("cba");
        System.out.println(strings);


        TreeSet<Person> people = new TreeSet<>();
        people.add(new Person("엄"));
        people.add(new Person("엄1"));
        people.add(new Person("엄4"));
        people.add(new Person("엄3"));
        people.add(new Person("엄"));

        // 해당 클래스는 implements Comparable<Person>로 인터페이스를 구현하여서 중복을 제거.
        System.out.println(people);
    }

중복제거 및 객체에 따른 정렬을 해준다.

다만 객체 타입의 비교를 위해선 comparable를 구현하여야 하며 비교 및 정렬을 할 필드를 설정해야함

class Person implements Comparable<Person>{
    private String name;

    public Person(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                '}';
    }

    @Override
    public int compareTo(Person o) {
        return name.compareTo(o.name);
    }
}