[자료구조] 배열(Array)과 연결 리스트(Linked List)

📌 배열

---

🔍 배열(Array)이란?

배열은 CRUD를 할 때 가장 기본적으로 사용되는 자료구조이다.

생성할 때 크기가 결정되고 각 자리에 대해 인덱스 번호가 부여된다. 인덱스 번호를 통해 배열 내부에 있는 요소들에 접근할 수 있다.

위와 같이 배열의 주소를 나타내는 인덱스(index)와 요소(elements)로 구성되어 있다.

배열의 장점

배열은 필요에 따라 바로 생성하여 사용하기 용이하다.

int[] numArr = { 1, 2, 3, 4, 5 };

와 같이 배열은 바로 생성할 수 있다는게 최고 장점이다.

그리고 배열이 응용되어 스택이나 큐 같은것들이 존재한다고 볼 수 있기 때문에 배열은 어떤 자료구조의 기초가 될 수 있다.

또한 원하는 데이터에 대해 CRUD를 쉽게 처리할 수 있으며 정렬하기에 용이하다는 장점을 갖는다.

배열의 단점

배열의 단점은 바로 생성 시 크기가 결정되기 때문에 유연하지 못하다. 즉 데이터를 저장할 수 있는 메모리의 크기가 고정되어 있으며 이를 동적으로 바꿀 수 없다.

또한 데이터를 추가하거나 삭제하는 방법이 다소 비효율적이다. 예를 들어 위 사진의 배열에서 1번째와 2번째 사이에 새로운 요소를 넣는다고 가정하면, 배열은 크기가 고정되어 있고 입력받은 순서대로 들어가기 때문에 배열의 크기를 재지정해주고 맨 뒤로 들어간 새로 입력받은 요소를 1번째와 2번째 인덱스 사이까지 당겨와주는 작업이 필요하다.

배열 사용 예시

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        int[] numArr = new int [5];
        // 인덱스에 직접 값을 할당하는 방법
        numArr[0] = 1;
        numArr[1] = 2;
        numArr[2] = 3;
        numArr[3] = 4;
        numArr[4] = 5;

        System.out.println(Arrays.toString(numArr));

        // for loop로 배열을 순회하며 할당하는 방법
        String[] strArr = new String [5];
        for (int i = 0; i < strArr.length; i++) {
            strArr[i] = Integer.toString(i+1);
        }

        System.out.println(Arrays.toString(strArr));

        // 값 삭제
        numArr[0] = 0;      // 0으로 초기화

        // 또는
        for (int i = 0; i < numArr.length; i++) {
            numArr[i] = 0;
        }

        // fill 메서드 사용
        Arrays.fill(numArr, 0);

        // Null 참조 설정
        numArr = null;

    }
}

📌 연결 리스트(Linked List)

---

🔍 연결 리스트(Linked List)란?

앞서 소개한 배열과 스택, 큐는 메모리에 있는 데이터의 물리적 배치에 의존하는 자료구조라고 볼 수 있다. 반대로 Linked List는 메모리에 있는 데이터의 물리적 배치에 의존적이지 않다(사용하지 않는다).

배열의 index나 큐/스택의 위치 개념보다 참조 시스템을 사용하는데, 내부에 있는 각 요소들은 Node라는 것에 저장된다.

이는 다음 Node 연결에 대한 포인터 또는 주소가 포함된 또 다른 Node에 저장된다.

데이터가 들어가는 공간인 Data Field(데이터 필드)와 다음 노드로 연결되는 Link Field(링크 필드)로 구성되며 이 전체를 Node로 본다.

Node는 최소 두 가지 정보가 전제되어야 하는데, 이는 Node의 값과 다음 Node의 값이다. 각각의 Node가 다음 Node를 알고 연결되어 있기 때문에 하나의 모임을 만들어낼 수 있는 것이다.

비슷한 이름의 ArrayList는 Node라는 체계로 이루어져있기 보다 배열과 유사하다고 보면 된다.

연결 리스트는 데이터의 추가/삭제 시 재구성을 하지 않아도 알아서 Node끼리 다시 연결되기 때문에 매우 효율적이라고 말할 수 있다.

연결 리스트의 장점

우선 새로운 요소를 추가하거나 기존의 요소를 삭제할 때 Node가 알아서 연결되기 때문에 효율적이다.
배열처럼 메모리에 연속적으로 위치하지 않으며 CRUD간 구조의 재구성을 하지 않아도 된다.
배열처럼 크기가 제한적이지 않기 때문에 메모리를 동적으로 사용하여 대용량 데이터 처리를 할 때 유연하다.

연결 리스트의 단점

배열보다 더 많은 메모리를 사용한다.
검색 시 처음부터 끝까지 리스트를 순회하며 조회하기 때문에 원하는 값을 가져오는데 비효율적이다.
이중 연결 리스트인 경우 Node를 반대 방향으로 검색할 때 비효율적이다.

연결 리스트 사용 예시

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {

        // 연결 리스트 생성, 초기화
        LinkedList<Integer> list = new LinkedList<>();

        // 값 넣어주기
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // 조회
        System.out.println(list);

        // 값 삭제하기
        list.remove(0);     // 0번째 값 삭제
        System.out.println(list);   // 2, 3, 4, 5

        // 값 조회
        System.out.println(list.get(1));    // 1번째 값 출력 : 3

    }
}