⚠️Warning
본 포스트는 당일 학원에서 배운 내용을 복습하는 목적의 공부 기록 시리즈입니다. 정보 전달의 목적이 아님을 유의해주세요! 잘못된 내용에 대한 피드백을 환영합니다:)

---

❓ LinkedList란?

: List(Interface)의 구현 클래스 중 하나로 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.
중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

💡 Collection(I) → List(I) → ArrayList(C), LinkedList(C)

ArrayList vs LinkedList

• List 구현 → 사용법 아주 유사 → 개발자 경험
• But 내부 구조가 다르다. → 사용 용도가 다르다.

LinkedList 종류

1. LinkedList: 일방통행
2. Double LinkedList: 양방향 통행
3. Double Circle LinkedList: 양방향 + 처음~끝 연결 → java의 LinkedList

ArrayList vs LinkedList

ArrayList<Integer> list1 = new ArrayList<Integer>();

LinkedList<Integer> list2 = new LinkedList<Integer>();

💡 ArrayList

• 모든 컬렉션 중에서 요소에 접근하는 속도가 가장 빠르다.
• 요소 삽입/삭제에 대한 비용이 많이 든다. → Shift 有
• 우리 주변에는 중간에 데이터를 추가 하는 업무보단, 순차적으로 추가하는 업무가 많기 때문에 상대적으로 ArrayList가 더 많이 쓰임!

💡 LinkedList

• 요소에 접근 속도가 상대적으로 느리다.
• 요소 삽입/삭제에 대한 비용이 거의 없다. → Shift 無

📌 배열이 모든 collection중에서 값을 찾는 속도가 가장 빠르다
Why?) 해당 배열 index의 주소값을 바로 찾아서 이동하기 때문에 빠름.
ex) int[] list = new int[5]; list[2] (list[0]의 주소값이 100번지일 경우) → 100 + 4 * 2 = 108 → 바로 108번지 이동
(이런 식으로 바로 주소를 찾아서 이동하기 때문에 빠름!!!)

반면, LinkedList는 모든 주소값이 유기적으로 연결되어 있어 한번에 해당 방을 찾아갈 수 없기 때문에 순수 배열이나 ArrayList에 비해 속도가 느릴 수 밖에 없음!!

다만 용도에 따라 ArrayList 또는 LinkedList 사용이 더 나은 경우가 있으니, 용도에 맞게 선택해서 사용하면 됨!

사용법 비교

• 추가하기

  ArrayList<Integer> list1 = new ArrayList<Integer>();
  LinkedList<Integer> list2 = new LinkedList<Integer>();
  
  //ArrayList > add
  list1.add(10);
  list1.add(20);
  list1.add(30);
  
  //LinkedList > add
  list2.add(10);
  list2.add(20);
  list2.add(30);

• 사이즈 확인

  //ArrayList > size()
  System.out.println(list1.size()); //3
  
  //LinkedList > size()
  System.out.println(list2.size()); //3

• 각 방별 값 확인

  //ArrayList > get()
  System.out.println(list1.get(0)); //10
  System.out.println(list1.get(1)); //20
  System.out.println(list1.get(2)); //30
  
  //LinkedList > get()
  System.out.println(list2.get(0)); //10
  System.out.println(list2.get(1)); //20
  System.out.println(list2.get(2)); //30

작업 시간 비교

• 순차적으로 데이터 추가하기, Append
  • ArrayList 작업 시간 확인

    ArrayList<Integer> list1 = new ArrayList<Integer>();
    LinkedList<Integer> list2 = new LinkedList<Integer>();
    
    long begin = 0, end = 0;
    
    //순차적으로 데이터 추가하기, Append
    System.out.println("[순차적으로 데이터 추가하기, Append]");
    
    ////ArrayList 작업시간 확인
    begin = System.currentTimeMillis();
    
    for (int i=0; i<1000000; i++) {
    	list1.add(i); //배열 끝에 추가하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

  • LinkedList 작업 시간 확인

    begin = System.currentTimeMillis();
    
    for (int i=0; i<1000000; i++) {
    	list2.add(i); //배열 끝에 추가하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);

    ---

    //출력
    [순차적으로 데이터 추가하기, Append]
    ArrayList 작업 시간: 221ms
    LinkedList 작업 시간: 180ms

• 중간에 데이터 추가하기, 삽입(Insert) → Shift 발생
  • ArrayList 작업 시간 확인

    //중간에 데이터 추가하기, 삽입(Insert) > Shift 발생
    
    System.out.println("[중간에 데이터 추가하기, 삽입(Insert) > Shift 발생]");
    
    ////ArrayList 작업시간 확인
    begin = System.currentTimeMillis();
    
    for (int i=0; i<10000; i++) {
    	list1.add(0, i); //0번 방에 삽입하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

  • LinkedList 작업 시간 확인

    begin = System.currentTimeMillis();
    
    for (int i=0; i<10000; i++) {
    	list2.add(0, i); //0번 방에 삽입하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);

    ---

    //출력
    [중간에 데이터 추가하기, 삽입(Insert) > Shift 발생]
    ArrayList 작업 시간: 10,923ms
    LinkedList 작업 시간: 2ms

• 중간에 데이터 삭제하기 → Shift 발생
  • ArrayList 작업 시간 확인

    //중간에 데이터 삭제하기 > Shift 발생
    System.out.println("[중간에 데이터 삭제하기 > Shift 발생]");
    
    ////ArrayList 작업시간 확인
    begin = System.currentTimeMillis();
    
    for (int i=0; i<10000; i++) {
    	list1.remove(0); //0번 방 삭제하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

  • LinkedList 작업 시간 확인

    begin = System.currentTimeMillis();
    
    for (int i=0; i<10000; i++) {
    	list2.remove(0); //0번 방 삭제하기
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);

    ---

    //출력
    [중간에 데이터 삭제하기 > Shift 발생]
    ArrayList 작업 시간: 10,579ms
    LinkedList 작업 시간: 1ms
    	

• 순차적으로 데이터 삭제하기(끝→처음 index순으로 삭제) → Shift 불요
  • ArrayList 작업 시간 확인

    //순차적으로 데이터 삭제하기 > 끝 ~ 첫 방으로 삭제 > Shift 불요
    System.out.println("[순차적으로 데이터 삭제하기]");
    
    ////ArrayList 작업시간 확인
    begin = System.currentTimeMillis();
    
    for (int i=list1.size()-1; i>=0; i--) {
    	list1.remove(i); //끝 > 시작 삭제
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

  • LinkedList 작업 시간 확인

    begin = System.currentTimeMillis();
    
    for (int i=list2.size()-1; i>=0; i--) {
    	list2.remove(i); //끝 > 시작 삭제
    }
    
    end = System.currentTimeMillis();
    
    System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);

    ---

    //출력
    [순차적으로 데이터 삭제하기]
    ArrayList 작업 시간: 16ms
    LinkedList 작업 시간: 52ms