[자료구조] 배열 리스트, 연결 리스트

배열의 경우 2가지 불편함이 있었다.

• 배열의 길이를 동적으로 변경 불가.
• 데이터를 추가하기 힘들다.
• (데이터를 추가하는 경우 직접 오른쪽으로 한 칸씩 데이터를 미는 코드를 직접 작성해야 하기 때문)

배열의 이런 불편함을 해소하고 동적으로 데이터를 추가할 수 있는 자료 구조를 List(리스트)라 한다.

 

List 자료 구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다.

• 일반적으로 배열과 리스트는 구분해서 이야기한다. 
• 리스트는 배열보다 유연한 자료 구조로, 크기가 동적으로 변할 수 있다.
• (데이터가 추가되면 배열이 꽉 찰 때마다 자동으로 더 큰 배열을 할당하고 기존 데이터를 복사하는 방식으로 크기를 늘린다.)

배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다.
리스트: 순서가 있고 중복을 허용하지만 크기가 동적으로 변할 수 있다.

---

ArrayList

특징

• 동적 배열(Dynamic Array): ArrayList는 동적 배열로, 크기를 자동으로 조정할 수 있다. 배열의 크기가 꽉 차면, 새로운 더 큰 배열을 생성하고 기존 배열의 데이터를 복사한 후, 추가된 공간을 이용해 새로운 데이터를 삽입한다.
• 순서 보장: ArrayList는 삽입 순서를 유지합니다. 즉, 삽입된 순서대로 요소를 저장하고, 이 순서에 따라 접근할 수 있다.
• 중복 허용: 같은 값을 여러 번 저장할 수 있다. 즉, 동일한 값의 요소가 여러 번 등장할 수 있다.
• 빠른 조회: 배열을 기반으로 하므로, 인덱스를 통한 조회가 빠르며, 시간 복잡도는 O(1)이다.
• 비효율적인 삽입 및 삭제: 중간에 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 한 칸씩 이동해야 하기 때문에 시간 복잡도는 O(n)이 된다.
• 동적 확장: 기본 배열의 크기가 초과하면, ArrayList는 현재 배열 크기의 약 1.5배 또는 2배로 크기를 증가시킨다. 이때 모든 기존 요소를 새로운 배열로 복사하는 작업이 필요하다.

 

특징 - 동적 배열

배열의 크기를 초과할 때

• 정적인 배열과 다르게 크기가 동적으로 변하는 자료 구조이다. 
• 따라서 데이터의 크기를 미리 정하지 않아도 된다.
• 기존 배열(x001)은 더는 참조하는 곳이 없으므로 GC의 대상이 된다.

 

코드 예시)

public void add(Object e) {

    if (size == elementData.length) {
            grow();
        }
        elementData[size] = e;
        size++;
    }

    /**
     * 실제 삽입된 데이터(size)가 배열의 길이(capacity)와 같아지면
     * 기존 길이의 2배 배열을 생성하고, 기존의 데이터를 복사한다.
     */
    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity * 2;

        // 배열을 새로 만들고, 기존 배열을 새로운 배열에 복사한다.
        /*Object[] newArr = new Object[newCapacity];

        for (int i = 0; i < elementData.length; i++) {
            newArr[i] = elementData[i];
        }
        */
        
        Object[] newArr = Arrays.copyOf(elementData, newCapacity);
        
        // *** 참조 변경 ***
        elementData = newArr;
    }

• 배열을 새로 복사해서 만드는 연산은 배열을 새로 만들고 또 기존 데이터를 복사하는 시간이 걸리므로 가능한 줄이는 것이 좋다. 
• 이렇게 2배씩 증가하면 배열을 새로 만들고 복사하는 연산을 줄일 수 있다. 
• 반면에 배열의 크기를 너무 크게 증가하면 사용되지 않고 낭비되는 메모리가 많아지는 단점이 발생할 수 있다.
• 참고로 예제를 단순화 하기 위해 여기서는 2배씩 증가했지만, 보통 50% 정도 증가하는 방법을 사용한다.

 

정리

• 순서와 중복 허용: 삽입 순서를 유지하며, 중복 요소도 저장 가능.
• 빠른 조회: 인덱스를 사용해 빠르게 요소에 접근 가능.
• 비효율적인 중간 삽입/삭제: 중간에 삽입하거나 삭제할 경우, 많은 요소를 이동해야 하므로 비효율적.
• 동적 확장: 기본 배열의 크기가 초과하면, 현재 배열 크기의 약 1.5배 또는 2배로 크기를 증가시킨다. (복사 필요)

---

ArrayList - 데이터 추가 삭제 

 

데이터 추가

• add() 를 사용해서 데이터를 추가하는 경우 리스트의 마지막( size )에 데이터를 추가한다.
• 데이터를 리스트의 마지막에 추가하기 때문에 기존 데이터를 이동하지 않는다.
• size 를 배열의 index 로 사용하고 기존 데이터를 이동하지 않기 때문에 O(1)로 표현할 수 있다.

 

마지막에 추가

• add(index, e) 를 사용해서 원하는 위치에 데이터를 추가할 수 있다.
• 데이터를 리스트의 마지막에 추가하기 때문에 기존 데이터를 이동하지 않는다.
• O(1)로 표현할 수 있다.

 

앞에 추가

 

• add(index, e) 를 사용해서 원하는 위치에 데이터를 추가할 수 있다.
• 추가할 위치를 확보하기 위해 입력한 위치를 기준으로 데이터를 오른쪽으로 한 칸씩 이동해야 한다.
• 앞서 보았듯 마지막 위치에 추가하는 경우는 데이터를 이동하지 않는다.
• 데이터를 추가할 위치는 배열의 인덱스를 사용하므로 O(1)로 빠르게 찾을 수 있지만, 데이터를 이동하는데 O(n)이 소요된다.
• O(n)으로 표현할 수 있다.

 

데이터 삭제

 

마지막에 삭제

• remove(index) 를 사용해서 원하는 위치에 있는 데이터를 삭제할 수 있다.
• 이때 마지막 위치라면 기존 데이터를 이동할 필요가 없다.
• 참고로 데이터를 삭제하면 리스트의 크기인 size 가 하나 줄어든다.
• O(1)로 표현할 수 있다.

 

앞에 삭제

• remove(index) 를 사용해서 원하는 위치에 있는 데이터를 삭제할 수 있다.
• 이때 마지막 위치가 아니라면 삭제할 데이터의 위치를 기준으로 데이터를 한 칸씩 왼쪽으로 이동해야 한다.
• 데이터를 삭제할 위치는 배열의 인덱스를 사용하므로 O(1)로 빠르게 찾을 수 있지만, 데이터를 이동하는데 O(n)이 소요된다.
• O(n)으로 표현할 수 있다.

결과적으로 마지막에 위치한 데이터를 추가, 삭제할 때는 데이터의 이동이 필요없지만 그 외에는 모두 좌,우로 이동이 필요하다.

 

코드 예시)

public void add(int index, Object e) {
    if (size == elementData.length) {
        grow();
    }

    // 요소의 마지막부터 index까지 오른쪽으로 밀기
    for (int i = size; i > index; i--) {
        elementData[i] = elementData[i - 1];
    }

    elementData[index] = e;
    size++;
}

public Object remove(int index) {

    Object oldValue = get(index);
    // 요소의 index부터 마지막까지 왼쪽으로 밀기
    for (int i = index; i < size - 1; i++) {
        elementData[i] = elementData[i + 1];
    }
    size--;
    elementData[size] = null;
    return oldValue;
}

 

 

배열 리스트의 빅오

• 데이터 추가
  • 마지막에 추가: O(1)
  • 앞, 중간에 추가: O(n)
• 데이터 삭제
  • 마지막에 삭제: O(1)
  • 앞, 중간에 삭제: O(n)
• 인덱스 조회: O(1)
• 데이터 검색: O(n)

 

ArrayList의 단점

 

1. 정확한 크기를 미리 알지 못하면 메모리가 낭비된다.

• 배열의 사용하지 않는 공간 낭비
• 배열을 사용하므로 배열 뒷 부분에 사용되지 않고, 낭비되는 메모리가 있다.

 

2. 배열의 중간에 데이터 추가

• 데이터를 중간에 추가하거나 삭제할 때 비효율적이다.
  • 이 경우 데이터를 한 칸씩 밀어야 한다. 이것은 O(n)으로 성능이 좋지 않다.
  • 만약 데이터의 크기가 1,000,000건이라면 최악의 경우 데이터를 추가할 때 마다 1,000,000건의 데이터를 밀어야 한다.

 

정리

배열 리스트는 마지막에 데이터를 추가하거나 마지막에 있는 데이터를 삭제할 때는 O(1)로 매우 빠르지만, 중간에 데이터를 추가하거나 삭제하는 경우에는 O(n)으로 느리다. 배열 리스트는 보통 데이터를 중간에 추가하고 삭제하는 변경 보다는, 데이터를 순서대로 입력하고(데이터를 마지막에 추가하고), 순서대로 출력하는 경우에 가장 효율적이다.

---

LinkedList

특징

• 노드 기반 자료구조: LinkedList는 노드(Node)라는 구조로 데이터가 저장된다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터(참조값)를 가지고 있다. 자바의 LinkedList는 이중 연결 리스트(Doubly Linked List)로 구현되어, 각 노드가 이전 노드와 다음 노드를 가리킨다.
• 비연속적인 메모리 할당: ArrayList와 달리, LinkedList는 데이터가 메모리의 연속된 공간에 저장되지 않는다. 노드가 메모리의 다른 위치에 할당되며, 포인터를 통해 연결된다.
• 삽입/삭제에 유리: 노드 간 연결만 조정하면 되기 때문에, 리스트의 중간에 데이터를 삽입하거나 삭제하는 작업이 빠르다. 하지만 삽입할 위치를 찾기 위해서는 탐색이 필요하므로 전체 시간 복잡도는 O(n)이다.
• 순서 보장: LinkedList도 삽입된 순서를 유지합니다.
• 중복 허용: 동일한 값이 여러 번 저장될 수 있습니다.
• 느린 조회: LinkedList는 인덱스를 통한 조회가 O(n)의 시간이 걸립니다. 원하는 노드를 찾기 위해 처음 노드부터 차례대로 탐색해야 하기 때문이다.

 

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

 

노드 클래스 예시

public class Node {
    Object item;
    Node next;
}

• 노드 클래스는 내부에 저장할 데이터인 item 과, 다음으로 연결할 노드의 참조인 next 를 가진다.

 

노드에 데이터 A 추가

• Node 인스턴스를 생성하고 item 에 "A"를 넣어준다.

 

노드에 데이터 B 추가

• Node 인스턴스를 생성하고 item 에 "B"를 넣어준다.
• 처음 만든 노드의 Node next 필드에 새로 만든 노드의 참조값을 넣어준다.
• 이렇게하면 첫 번째 노드와 두 번째 노드가 서로 연결된다.
• 첫 번째 노드의 node.next 를 호출하면 두 번째 노드를 구할 수 있다.

 

연결된 노드를 찾는 방법

• Node first 를 통해 첫 번째 노드를 구할 수 있다.
• 첫 번째 노드의 node.next 를 호출하면 두 번째 노드를 구할 수 있다.
• 두 번째 노드의 node.next 를 호출하면 세 번째 노드를 구할 수 있다.
• 첫 번째 노드의 node.next.next 를 호출하면 세 번째 노드를 구할 수 있다.

 

정리

• 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
• 각각의 노드가 참조를 통해 연결(Link, 링크) 되어 있다.
• 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.
• 물론 next 필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
• 이렇게 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이것을 연결 리스트라 한다.

 

연결 리스트와 빅오

 

1. 조회

Object get(int index)

• 특정 위치에 있는 데이터를 반환한다.
• O(n)

배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있다. 따라서 배열을 사용하는 배열 리스트( ArrayList )도 인덱스로 조회시 O(1)의 빠른 성능을 보장한다. 하지만 연결 리스트에서 사용하는 노드들은 배열이 아니다. 단지 다음 노드에 대한 참조가 있을 뿐이다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자 만큼 다음 노드를 반복해서 찾아야 한다. 따라서 인덱스 조회 성능이 나쁘다. 특정 위치의 노드를 찾는데 O(n)이 걸린다.

 

2. 추가

void add(Object e)

 

• 마지막에 데이터를 추가한다.
• O(n)

마지막 노드를 찾는데 O(n)이 소요된다. 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서O(n)이다.

이중 연결 리스트의 경우는 O(1) 이다. 마지막 노드의 참조값을 가지고 있기 때문이다.

 

3. 수정

Object set(int index, Object element)

 

• 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
• O(n)

특정 위치의 노드를 찾는데 O(n)이 걸린다.

 

4. 검색

int indexOf(Object o)

 

• 데이터를 검색하고, 검색된 위치를 반환한다.
• O(n)

모든 노드를 순회하면서 equals() 를 사용해서 같은 데이터가 있는지 찾는다.

 

정리

• 연결 리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용한다. 
• 따라서 배열 리스트의 단점인 메모리 낭비를 해결할 수 있다.
• 물론 연결을 유지하기 위한 추가 메모리가 사용되는 단점도 함께 존재한다

---

LinkedList - 데이터 추가 삭제 

 

 

데이터 추가

첫 번째 위치에 데이터 추가

 

1. 신규 노드 생성

 

 

2. 신규 노드와 다음 노드 연결

 

 

3. first에 신규 노드 연결

 

 

 

최종 결과

• 노드를 추가했으므로 오른쪽 노드의 index가 하나씩 뒤로 밀려난다.
  
  • 연결 리스트는 배열처럼 실제 index가 존재하는 것이 아니다. 
  • 처음으로 연결된 노드를 index 0, 그 다음으로 연결된 노드를 index 1로 가정할 뿐이다. 
• 연결 리스트에서 index는 연결된 순서를 뜻한다.
• 배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
• 연결 리스트의 첫 번째 항목에 값을 추가하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

중간 위치에 데이터 추가

 

1. 새로운 노드를 생성하고, 노드가 입력될 위치의 직전 노드(prev)를 찾아둔다.

 

• 여기서 인덱스 1번의 직전 노드는 인덱스 0번 노드이다.

 

2. 신규 노드와 다음 노드를 연결한다. 직전 노드(prev)의 다음 노드를 연결하면 된다.

 

 

3. 직전 노드(prev)에 신규 노드를 연결한다.

 

최종 결과

• 노드를 추가했으므로 추가한 노드 오른쪽에 있는 노드들의 index가 하나씩 뒤로 밀려난다.
• 배열의 경우 데이터가 추가되면 인덱스 위치 부터 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
• O(n)의 성능이다.
  
  • 연결 리스트는 인덱스를 사용해서 노드를 추가할 위치를 찾는데 O(n)이 걸린다.
  • 위치를 찾고 노드를 추가하는데는 O(1)이 걸린다.
  • 따라서 둘을 합하면 O(n)이 걸린다.

 

 

데이터 삭제

첫 번째 위치의 데이터 삭제

 

1. 삭제 대상 선택

 

 

2. first에 삭제 대상의 다음 노드 연결

 

 

3. 삭제 대상의 데이터 초기화

• 더는 삭제 노드를 참조하는 곳이 없다. 이후 삭제 노드는 GC의 대상이 되어서 제거된다.

 

최종 결과

• 드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨진다.
• 배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만 연결 리스트는 일부 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
• 연결 리스트의 첫 번째 항목에 값을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

 

 

중간 위치의 데이터 삭제

 

1. 삭제 대상을 찾는다. 그리고 삭제 대상의 직전 노드(prev)도 찾아둔다.

 

 

 

2. 직전 노드(prev)의 다음 노드를 삭제 노드의 다음 노드와 연결한다.

 

 

3. 삭제 노드의 데이터를 초기화 한다.

• 더는 삭제 노드를 참조하는 곳이 없다. 삭제 노드는 이후 GC의 대상이 되어서 제거된다.

 

최종 결과

• 노드를 삭제했으므로 오른쪽 노드의 index가 하나씩 당겨진다. O(n)의 성능이다.
• 연결 리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸린다.
• 연결 리스트에서 항목을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.
• 연결 리스트와 배열 리스트 둘다 중간에 있는 항목을 추가하거나 삭제하는 경우 둘다 같은 O(n)이다.

---

ArrayList VS LinkedList

상황별 성능 비교

 

배열 리스트와 연결 리스트의 전체 성능 비교

 

 

참고 - 단일 연결 리스트, 이중 연결 리스트

• 자바가 제공하는 연결 리스트는 이중 연결 리스트다.
• 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 삭제하는 경우에도 O(1)의 성능을 제공한다.

 

이중 연결 리스트 예시)

public class Node {
    Object item;
    Node next; //다음 노드 참조
    Node prev; //이전 노드 참조
}

 

 

마지막 노드를 참조하는 연결 리스트

public class LinkedList {
    private Node first;
    private Node last; //마지막 노드 참조
    private int size = 0;
}

 

 

시간 복잡도와 실제 성능

 

이론적으로 LinkedList 의 중간 삽입 연산은 ArrayList 보다 빠를 수 있다. 

그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
추가로 ArrayList 는 데이터를 한 칸씩 직접 이동하지 않고, 대신에 메모리 고속 복사를 사용한다.
ArrayList 는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
반면, LinkedList 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다.

ArrayList 의 경우 배열의 크기를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가된다.

하지만 한번에 50%씩 늘어나기 때문에 이 과정은 가끔 발생하므로, 전체 성능에 큰 영향을 주지는 않는다.
정리하면 이론적으로 LinkedList 가 중간 삽입에 있어 더 효율적일 수 있지만,

현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList 가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다고 한다.

 

 

배열 리스트 vs 연결 리스트

• 대부분의 경우 배열 리스트가 성능상 유리하다.
• 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다고 한다.
• 만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

---