배열(Array) 와 링크드리스트(Linked List)

배열과 링크드리스트는 둘 다 컴퓨터 과학에서 사용하는 기본적인 데이터 구조입니다 .

데이터의 크기가 고정되어 있고, 특정 요소에 빠르게 접근해야 하는 경우에는 배열을 사용하는 것이 좋습니다.
반면에, 데이터의 크기가 동적으로 변하고, 요소의 추가와 삭제가 빈번한 경우에는 링크드리스트를 사용하는 것이 좋습니다.

 

배열과 링크드리스트는 데이터를 저장하는 방식이 다릅니다.

배열은:

• 데이터를 연속적인 메모리 공간에 저장합니다. 즉, 한 줄로 나란히 놓는 것을 생각하시면 됩니다.
• 각 데이터는 번호(인덱스)가 있어서 바로 접근할 수 있습니다.
• 하지만 나머지 데이터를 이동시켜야 하기 때문에 크기를 변경하거나 중간에 데이터를 추가하거나 삭제하는 것은 번거롭습니다.
• • 배열은 고정된 크기를 가지며, 연속된 메모리 공간에 동일한 타입의 데이터를 저장합니다.
  • 배열의 각 요소는 인덱스를 통해 직접 접근할 수 있으므로, 특정 요소에 대한 조회는 O(1)의 시간 복잡도를 가집니다.
  • 하지만, 배열의 크기는 생성 시점에 결정되며 변경할 수 없기 때문에, 크기를 확장하거나 축소하려면 전체 배열을 복사해야 합니다. 이는 O(n)의 시간 복잡도를 가집니다.
  • 배열에 요소를 추가하거나 삭제하는 연산도 O(n)의 시간 복잡도를 가집니다. 왜냐하면 요소를 추가하거나 삭제한 후에 배열의 다른 요소들을 이동해야 하기 때문입니다.

public class ArrayExample {
    public static void main(String[] args) {
        // 크기가 5인 정수 배열 생성
        int[] array = new int[5];

        // 배열에 값 할당
        for(int i=0; i<array.length; i++) {
            array[i] = i * 2;
        }

        // 배열 출력
        for(int i=0; i<array.length; i++) {
            System.out.println("Element at index " + i + ": " + array[i]);
        }
    }
}

링크드리스트는:

• 각 데이터(노드)가 다음 데이터를 가리키는 방식으로 저장합니다. 이런 노드들이 연결되어 있는 것을 생각하시면 됩니다.
• 데이터를 추가하거나 삭제하는 것은 쉽지만, 특정 데이터를 찾으려면 처음부터 하나씩 따라가야 합니다.
• 따라서 중간에 데이터를 추가하거나 삭제하는 경우에 유용합니다.
• 링크드리스트는 동적인 크기를 가지며, 비연속적인 메모리 공간에 데이터를 저장합니다. 각 요소(노드)는 데이터와 다음 노드에 대한 참조를 가지고 있습니다.
• 링크드리스트의 요소는 인덱스를 통해 직접 접근할 수 없으므로, 특정 요소에 대한 조회는 O(n)의 시간 복잡도를 가집니다. 왜냐하면 특정 요소를 찾기 위해 리스트를 순회해야 하기 때문입니다.
• 하지만, 링크드리스트는 동적으로 크기를 변경할 수 있으므로, 요소를 추가하거나 삭제하는 연산은 O(1)의 시간 복잡도를 가질 수 있습니다. 하지만 이는 해당 위치의 참조가 이미 알려져 있을 때만 가능합니다. 그렇지 않은 경우에는 O(n)의 시간 복잡도를 가집니다.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // LinkedList 생성
        LinkedList<String> linkedList = new LinkedList<>();

        // LinkedList에 요소 추가
        linkedList.add("Element 1");
        linkedList.add("Element 2");
        linkedList.add("Element 3");

        // LinkedList 출력
        for(int i=0; i<linkedList.size(); i++) {
            System.out.println("Element at index " + i + ": " + linkedList.get(i));
        }
    }
}

 

** 노드(Node)는 데이터를 담는 공간입니다.

예를 들어, 링크드리스트에서는 각 데이터가 저장되는 곳을 '노드'라고 부릅니다.

또한, 링크드리스트의 노드는 다음 노드를 가리키는 정보도 함께 저장하고 있습니다.

 

** O(n)의 시간 복잡도는 컴퓨터가 어떤 일을 하는데 걸리는 시간을 나타내는 표현 방식 중 하나입니다.

여기서 'n'은 데이터의 개수를 의미하고, O(n)은 '데이터 개수에 비례하여 시간이 걸린다'는 의미입니다.

예를 들어, 데이터가 10개 있을 때 10초가 걸리면, 데이터가 100개 있을 때는 100초가 걸린다는 뜻입니다.

간단히 말해, 배열에서는 어떤 데이터를 찾아가는데 한번에 갈 수 있지만,

링크드리스트에서는 첫 번째 데이터부터 하나씩 따라가며 찾아야 해서 시간이 더 걸린다는 것입니다.

이 때문에 링크드리스트에서 데이터를 찾는 시간을 O(n)으로 표현합니다.

 

**O(1)의 시간 복잡도는 어떤 작업을 수행하는 데 걸리는 시간이 데이터의 개수와 상관없이 항상 일정하다는 것을 의미합니다.

배열에서 특정 위치의 데이터에 바로 접근하는 것은 O(1)의 시간 복잡도를 가집니다.

왜냐하면 배열에서 각 데이터는 인덱스를 통해 바로 접근할 수 있기 때문입니다.

배열의 크기가 늘어나도, 특정 위치의 데이터에 접근하는데 걸리는 시간은 변하지 않습니다.

Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에서 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태로 존재한다. Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다. Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다. 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다. 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.

 

추가/삭제가 많다면 링크드리스트, 탐색/정렬이 많다면 배열을 사용하는 게 유리하다. 둘 다 선형 데이터 구조지만, 배열은 물리적으로도 연속된 메모리를 사용하고 링크드리스트는 다음 노드의 위치를 저장함으로써 흩어진 메모리를 연결해서 쓴다는 게 둘 사이의 차이점을 만드는 주요한 요인이다. 링크드리스트의 장점은 데이터의 추가/삽입 및 삭제가 용이하다. 즉, 새로운 노드를 끼워넣기 쉽다. 길이를 동적으로 조절 가능하다. 단점은 인덱스없이 연결관계만 있기 때문에 특정 노드를 불러내기 어렵다. (일반적으로) O(N)이 걸리며 순차적으로 탐색하게 되기 때문이다.(B+tree자료구조 등은 예외) 거꾸로 탐색하기도 어렵다. 정렬은 O(NlogN)이 걸린다. 배열의 장점은 자료마다 인덱스가 있어서 특정 자료를 불러내기 편하다. 단점은 연속된 메모리 공간을 할당받아야 하다보니 크기를 크게 키우기가 어렵다. 또한, 안 쓰는 공간까지 전부 예약해두고 있어야 하므로 공간 낭비가 생긴다.

 

배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이며 메모리상에서 연속적으로 저장되어 있는 특징을 갖기 때문에 index를 통한 접근이 용이하다는 장점이 있으나 삽입/삭제가 오래 걸리고 배열 중간의 데이터가 삭제 되면 공간 낭비가 발생할 수 있는 단점이 존재합니다. 링크드리스트(연결리스트)는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있는 트리(tree)구조의 근간이 되는 자료구조입니다. 배열과 달리 메모리를 연속적으로 사용하지 않아 삽입/삭제에 용이하다는 장점이 있습니다. 그러나 index로 임의 접근이 불가하며 처음부터 탐색을 해야하는 단점이 있습니다. 따라서 배열은 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용하고 링크드리스트는 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용합니다.

 

** 배열,링크드리스트 사용 예시:

영화관의 좌석 배치의 경우 각 좌석은 행과 열에 따라 정확한 위치를 가지고 있습니다.

이러한 좌석 배치는 '배열'과 유사하게 생각할 수 있습니다.

좌석의 번호(예: A열 5번)를 알면, 해당 좌석을 즉시 찾아갈 수 있습니다. 이렇게 빠르게 접근이 가능한 것은 배열의 특징입니다.

하지만 한번 정해진 좌석 배치(배열의 크기)는 변경하기 어렵습니다.

즉, 중간에 좌석을 추가하거나 제거하기는 어렵다는 것이 배열의 단점입니다.

기차의 경우 각각의 칸(= 노드)이 연결되어 있습니다.

각 칸은 다음 칸을 '가리키고' 있습니다. 이것이 바로 링크드리스트의 구조입니다.

기차는 필요에 따라 칸을 추가하거나 제거할 수 있습니다. 이렇게 동적으로 크기를 변경하는 것이 링크드리스트의 장점입니다.

하지만, 특정 칸에 바로 접근하려면 기차의 첫 칸부터 시작해서 원하는 칸을 찾을 때까지 한 칸씩 이동해야 합니다.

이렇게 특정 위치에 접근하는 데에 시간이 더 걸리는 것이 링크드리스트의 단점입니다.