JAVA의 LinkedList

ArrayList에 이어서 LinkedList에 대해 알아보겠습니다. 

LinkedList에서 가장 중요한 것은 노드입니다.

객체 Node는 data 필드와 next 포인터 변수를 가지고 있는 구조입니다.

각 노드는 다음 노드를 가리키는 하나의 참조만을 갖기 때문에 접근이 한 방향으로만 가능합니다.

public static void main(String[] args) {
    LinkedList<Integer> numbers = new LinkedList<>();
    numbers.add(10);
    numbers.add(20);
    numbers.add(30);
    numbers.add(40);
    System.out.println("add : " + numbers);

LinkedList를 사용하기 위해서는 우선 LinkedList 객체를 생성해야 합니다.

요소를 추가할 때는 위와 같이 add 메소드를 사용합니다.

LinkedList는 배열과 달리 삽입하고 싶은 위치로 이동해야 합니다.

배열은 원하는 인덱스에 바로 삽입한 뒤 나머지 데이터를 옆으로 한 칸씩 이동했지만

연결리스트는 링크를 따라서 원하는 위치로 이동한 뒤 앞 뒤 링크를 연결시켜주면 됩니다.

따라서 앞이나 뒤에 있는 데이터의 경우 배열리스트 보다 속도가 더 빠를 수 있습니다.

    numbers.remove(2);
    System.out.println("removeIndex : " + numbers);
    numbers.removeAll(numbers);

연결리스트에서 삭제 연산은 링크를 따라 이동한 뒤 원하는 위치의 노드를 삭제합니다.

원하는 인덱스에 위치하는 노드를 삭제할 때는 remove 함수를 사용합니다.

LinkedList 내의 모든 노드를 삭제하고 싶을 때는 removeAll 함수를 사용합니다.

    System.out.println("getIndex : " + numbers.get(2));
    System.out.println("getSize : " + numbers.size());
    System.out.println("indexOf : " + numbers.indexOf(30));

원하는 인덱스의 노드를 꺼내고 싶을 땐 get 함수를

전체 리스트의 크기를 알고 싶을 땐 size 함수를

노드 값의 인덱스를 알고 싶을 땐 indexOf 함수를 사용합니다.

    for(int i = 0; i < numbers.size(); i++) {
        System.out.print(numbers.get(i)+ " ");
    }
        
    for(int value : numbers) {
        System.out.print(value+ " ");
    }

LinkedList의 모든 요소를 출력하는 방법 2가지가 있습니다.

하나는 리스트의 사이즈만큼 for문을 돌려서 얻는 방법,

두번째는 numbers 내의 모든 노드들을 하나씩 반환하여 출력하는 방법입니다.

    int[] value = {10, 20, 30, 40};
    for(int i = 0; i < value.length; i++) {
        numbers.add(value[i]);
    }
 
    for(int number : numbers) {
        System.out.print(number+ " ");
    }

다음은 정의된 배열의 값을 LinkedList로 저장하는 방법입니다.

---

JAVA ArrayList와 LinkedList의 비교

데이터가 적은 경우엔 별 차이가 없지만 데이터가 100만개 있다고 가정했을 때

어떤 연산의 경우에 어느 것이 더 효율적인지 비교해보겠습니다.

1. 삽입 연산의 경우

 - ArrayList < LinkedList (빠름)

 - ArrayList는 shift 연산이 일어나기 때문입니다.

* 순차적으로 삽입하는 경우에는 ArrayList가 빠릅니다.

2. 삭제 연산의 경우

 - ArrayList < LinkedList (빠름)

 - 삽입연산과 마찬가지 이유 때문입니다.

* 순차적으로 삭제하는 경우에는 ArrayList가 빠릅니다.

3. 탐색 연산의 경우

 - ArrayList (빠름) > LinkedList

 - LinkedList는 링크를 따라 이동해야 하기 때문입니다.

4. 메모리의 사용량

 - ArrayList (많음) > LinkedList

 - ArrayList는 JAVA 내부에서 배열을 복사하여 크기를 늘리기 때문에 제한적입니다.

 - LinkedList는 동적 생성이 가능합니다.

* 참고자료 : https://opentutorials.org/module/1335/8857