리스트란?

배열의 한계를 극복할 수 있는 자료 구조 중의 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있다. 순차적으로 데이터를 저장하고 관리하는 데 사용되며, 자바에서는 ArrayList와 LinkedList 같은 다양한 리스트 구현체를 제공한다.
배열처럼 어떠한 데이터들을 묶기 위한 개념이며, 배열과의 차이는 데이터를 담을 공간의 추가가 가능하다는 점이다.

리스트의 특징

• 순차 저장: 데이터가 순차적으로 저장된다.
• 인덱스 접근: 배열과 유사하게 인덱스를 통해 요소에 접근할 수 있다.
• 크기 가변: 배열과 달리, 리스트의 크기는 동적으로 변경될 수 있다.

리스트의 종류

ArrayList

내부적으로 배열을 사용하여 요소를 저장한다. 요소에 대한 인덱스 접근이 빠르지만, 요소의 삽입 및 삭제가 느리다.

LinkedList

내부적으로 연결 리스트를 사용하여 요소를 저장한다. 인덱스 접근이 느리지만, 요소의 삽입 및 삭제가 빠르다.

리스트 예제 (자바)

ArrayList

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // ArrayList 생성
        ArrayList<String> list = new ArrayList<>();

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 요소 조회
        System.out.println("첫 번째 요소: " + list.get(0)); // Apple

        // 요소 제거
        list.remove("Banana");

        // 전체 출력
        for (String fruit : list) {
            System.out.println(fruit);
        }
    }
}

LinkedList

import java.util.LinkedList;

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

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 요소 조회
        System.out.println("첫 번째 요소: " + list.get(0)); // Apple

        // 요소 제거
        list.remove("Banana");

        // 전체 출력
        for (String fruit : list) {
            System.out.println(fruit);
        }
    }
}

---

연결 리스트(Linked List)

노드(Node)의 연결로 이루어진 자료구조이다.

노드(Node)
연결 리스트에서 데이터를 구성하는 요소이다.
데이터, 연결 정보(링크)로 구성되어 있다.

노드의 구조

노드는 데이터와 다음 노드를 가리키는 링크(next)로 구성되어 있다.
제일 앞에 있는 노드를 헤드(head), 제일 끝에 있는 노드를 테일(tail)이라고 한다.

연결 리스트의 장단점

장점

가장 큰 장점은 리스트의 길이가 가변적이라는 것이다.

• 배열은 크기가 가변적이지 않아서 크기를 정해준 다음에 부족하면 메모리를 더 할당하고, 배열의 데이터를 복사해야 한다.
• 하지만 연결 리스트는 다음 노트만 추가하면 되기 때문에 리스트의 사이즈를 조정하는 데 큰 비용을 들이지 않는다.

단점

어떤 노드를 검색하거나 데이터를 변경할 때 바로 찾아낼 수가 없다. 최악의 경우 연결 리스트의 모든 노드를 전부 탐색해야 할 수 있다.

연결 리스트가 사용될 때는?

음악을 들을 때

자신의 플레이 리스트에서 자동으로 다음 음악이 재생될 때 사용된다.

방문한 웹 페이지 리스트

실제 stack이나 queue를 구성하는데도 연결 리스트를 활용 한 것이다.

Array VS Linked List

input size

• 배열 < 리스트
• 얼마나 들어오는지 모르는 상황에서 유동적으로 메모리 할당을 조절할 수 있는 리스트가 더 유리하다.

중간 데이터를 추가, 삭제할 때

• 배열 < 리스트
• 배열의 경우 중간에 값을 추가/삭제하게 되면 인덱스 번호가 이동된다. 하지만 리스트의 경우 링크의 연결만 바꿔주면 되어 리스트가 더 유리하다.

데이터의 검색

• 배열 > 리스트
• 배열은 인덱스를 지정해서 값을 빠르게 찾을 수 있지만, 리스트는 하나씩 찾아야 하기 때문에 배열이 더 유리하다.

마무리

• 데이터의 탐색은 배열 !
• 데이터가 가변적일 땐 연결 리스트 !

---

참고 자료

• https://jin-network.tistory.com/128