List

중복을 허용하고 순서대로 데이터를 저장하는 추상 데이터 자료형(ADT; Abstract Data Type)
자바에서 구현체로는 ArrayList와 LinkedList가 있다.

사용 사례

프로그래밍 언어 순위를 저장하려는 경우,
학번 순 대로 학생들을 저장하려는 경우 등
순서대로 저장할 필요가 없더라도, 꼭 Set이나 Map 등을 사용해야 하는 경우가 아니라면 대체로 List를 사용한다.

ArrayList

배열을 사용하여 리스트를 구현하였기 때문에 연속적인 공간에 순차적으로 데이터를 저장한다.

배열과 ArrayList

배열은 크기를 지정하고, 해당 크기 만큼의 연속된 메모리 공간을 할당받는 자료형이다. 배열의 단점은 크기가 고정되어, 한번 생성된 배열은 크기를 변경할 수 없다는 것이다. 크기를 예측할 수 없다면 너무 적은 영역을 할당해 모자라거나 너무 큰 영역을 할당해 낭비될 수 있다. 그럴때마다 개발자가 직접 새 배열을 생성해 기존 배열의 값을 복사해주어야 하는 불편함이 있다.

이러한 문제를 해결하고자 나온 것이 동적 배열이다.
동적 배열은 크기를 미리 지정하지 않고 자동으로 resizing하는 배열이다.
자바가 지원하는 동적배열은 ArrayList, C++은 std::vector이다.
파이썬과 루비 같은 언어는 편의를 위해 동적 배열만 제공한다.

자바의 ArrayList는 초기값으로 크기가 10인 배열을 생성하고, 공간이 가득차면 늘려주고 복사하는 방식이다. 이것을 Doubling이라 하며, 재할당 비율을 Growth Factor라고 한다.
자바는 아래와 같이 비트 연산으로 계산하도록 구현되어 있으며 이 비율은 정확히 1.5배이다.
int newCapacity = oldCapacity + (oldCapacity >> 1);

장점

• Indexing이 가능하여 상수 시간 O(1)에 원하는 위치의 값을 찾을 수 있다.

단점

• 배열이 가득 찰 경우 Doubling으로 인해 최악의 경우 O(N) 시간이 소요된다. 하지만 자주 발생하는 일은 아니므로 분할 상환 분석에 따른 시간복잡도는 O(1)이다.
• 삽입/삭제 시 데이터 쉬프트가 발생하여 최악의 경우 O(N) 시간이 소요된다.

배열이 빠른 조회가 가능한 이유는
2번째에 있는 값을 알고 싶을 때, 0x1001 주소로부터 (2-0)x4 만큼 떨어진 곳인 0x1009라는 주소를 찾아가 해당 위치에 저장된 14라는 값을 바로 찾을 수 있기 때문이다. *(int는 4byte)
배열이 1억개라도 마찬가자지이다. 즉시 주소를 계산할 수 있고, 언제든 해당 메모리 주소에 있는 값을 O(1)에 조회 가능하다.

LinkedList

노드를 연결(Link)을 통해 리스트를 구현하였기 때문에 비연속적인 공간에 순차적으로 데이터를 저장한다.
자바에서 연결리스트를 구현한 자료형은 LinkedList이며, 연결리스트의 특성상 다양한 인터페이스를 제공한다. 리스트가 될 수 있고, 큐, 데크가도 될 수 있다.
자바의 LinkedList는 이중 연결 리스트(Doubly Linked List)이다.
텍스트

장점

• ArrayList처럼 배열 복사나 데이터 쉬프트가 필요하지 않다.
• 동적으로 새로운 노드를 삽입/삭제하기가 간편하다.
• 연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되므로 관리가 쉽다.

단점

• 데이터 조회/검색/삽입/삭제 등 모든 경우에, 원하는 데이터를 처음부터 탐색해야 한다.

코드와 그림으로 보는 연결리스트

// 실제 자바의 LinkedList 코드 (대충 이런식임)
public class LinkedList<E> {
	int size;
	Node first;
    Node last;
     
	... // 생성자들, 메소드들
    
    
    private static class Node<E> {
    	E item;
        Node<E> next;
        Node<E> prev;
        
        ... // 생성자
    }
}

자바의 LinkedList는 연결리스트의 처음 item과 마지막 item을 참조하는 first, last 필드를 가지고 있고, 모든 요소의 개수를 담는 size 필드를 가지고 있다.
또한 노드 각각은 다음 노드의 참조값만 가지는 것이 아니라 이전 노드도 참조값도 가지고 있다.

// LinkedList의 사용
public class Student {
	String name;
    
    public Student(String name) {
     	this.name = name;
    }
}

public class Main {
	public static void main(String[] args) {
    	List<Student> stdents = new LinkedList<>();
        students.add(new Student("이은빈"));
        students.add(new Student("주효림"));
        students.add(new Student("김현민"));
    }
}

자바의 메모리 구조에 대해서 잘 모른다면 자바의 메모리 구조와 static을 보고 오자!

💡 Java의 LinkedList는 Doubly Linked List

나 왜 Circular로 알고 있었니?;;

ArrayList vs LinkedList

add at last index

• ArrayList : O(1)
• LinkedList : O(1)

add at given index

• ArrayList : O(N), 데이터의 쉬프트가 발생하므로
• LinkedList : O(1), 탐색 시간은 O(N)

remove by index

• ArrayList : O(N), 데이터의 쉬프트가 발생하므로
• LinkedList : O(1), 탐색 시간은 O(N)

remove by value

• ArrayList : O(N), 탐색 시간 발생, 데이터의 쉬프트 발생
• LinkedList : O(1), 탐색 시간은 O(N)

get by index

• ArrayList : O(1)
• LinkedList : O(N)

search by value

• ArrayList : O(N)
• LinkedList : O(N)

정리

• ArryList는 배열을 사용하여 List를 구현하였고, 연속적인 공간에 순차적으로 데이터를 저장한다.
  LinkedList는 노드의 연결을 사용하여 List를 구현하였고, 비연속적인 공간에 순차적으로 데이터를 저장한다.
• 인덱스를 통한 데이터의 접근 시간은 ArrayList의 경우, 모든 데이터에 상수 시간에 접근 가능하며 LinkedList는 위치에 따라 이동 시간이 발생한다.
• 두 자료구조 모두 삽입/삭제 자체는 상수 시간에 가능하지만 ArrayList는 데이터의 쉬프트로 인해 추가적인 시간이 발생하고, LinkedList는 삽입/삭제할 위치까지 이동하는 시간이 발생한다.
• ArrayList는 배열 확장이 필요한 경우 새로운 배열에 복사하는 시간이 발생한다. 하지만 분할상환분석에 따른 시간 복잡도는 O(1)이다.
• 검색 시간은 두 구현체 모두 최악의 경우 리스트에 있는 모든 아이템 수만큼 탐색해야 한다.
• ArrayList는 CPU Cache의 이점을 활용한다. -> 나중에 더 알아보기!!

참고

• 쉬운코드 - ArrayList와 LinkedList
• 책 자바 알고리즘 인터뷰 - 7장 배열

* 쉬운코드 유튜브, 자바 알고리즘 인터뷰 책 추천!! 자바 알고리즘 인터뷰는 문제 해설 부분은 약간 아쉽지만 그 전에 개념 설명 부분들은 문장 하나하나 핵심이 담겨있음.