24.12.30 TIL 배열과 링크드리스트

신성훈·2024년 12월 30일

링크드리스트 배열

TIL

목록 보기

109/162

1. 배열(Array)

1) 배열이란?

배열은 고정 크기의 메모리 공간에 연속적으로 저장된 데이터를 관리하는 자료구조입니다.
각 데이터는 인덱스를 통해 빠르게 접근할 수 있습니다.

2) 배열의 특징

빠른 접근 속도: 인덱스를 통해 O(1)의 시간 복잡도로 데이터 접근 가능
고정 크기: 크기가 정해져 있어 저장 공간의 크기를 초과하면 새로운 배열을 생성해야 함
연속된 메모리 할당: 데이터가 메모리의 연속된 공간에 저장됨

3) 배열의 장단점

장점	단점
데이터 접근 속도가 빠름	크기 변경이 어려움 (고정 크기)
간단한 구조로 메모리 사용 효율적	삽입 및 삭제가 비효율적 (O(n))

4) 배열 예제 코드

public class ArrayExample {
    public static void main(String[] args) {
        int[] array = {10, 20, 30, 40};

        // Access
        System.out.println("Element at index 2: " + array[2]); // 30

        // Update
        array[2] = 50;

        // Loop through array
        for (int num : array) {
            System.out.print(num + " ");
        }
        // Output: 10 20 50 40
    }
}

2. 링크드 리스트(Linked List)

1) 링크드 리스트란?

링크드 리스트는 노드(Node)라는 객체가 포인터를 통해 서로 연결된 구조의 자료구조입니다.
각 노드는 데이터와 다음 노드의 주소(참조)를 포함합니다.

2) 링크드 리스트의 종류

단일 연결 리스트(Singly Linked List): 한 방향으로만 연결
이중 연결 리스트(Doubly Linked List): 양방향으로 연결
원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드와 연결

3) 링크드 리스트의 특징

동적 크기: 데이터를 삽입/삭제할 때 메모리 동적으로 할당
비연속적인 메모리 저장: 각 노드가 독립적으로 메모리에 저장
느린 접근 속도: 특정 인덱스의 데이터 접근은 O(n) 소요

4) 링크드 리스트의 장단점

장점	단점
삽입/삭제가 용이 (O(1), 처음/끝)	데이터 접근이 느림 (O(n))
크기가 동적으로 변할 수 있음	추가적인 메모리 사용(포인터 저장 공간)

5) 링크드 리스트 예제 코드

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        Node head = new Node(10);
        head.next = new Node(20);
        head.next.next = new Node(30);

        // Traverse and print linked list
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        // Output: 10 20 30
    }
}

3. 배열과 링크드 리스트의 비교

특징	배열(Array)	링크드 리스트(Linked List)
메모리 할당	연속적인 메모리 공간	비연속적인 메모리 공간
크기	고정 크기	동적 크기
데이터 접근	빠름 (O(1))	느림 (O(n))
삽입/삭제	비효율적 (O(n))	효율적 (O(1), 처음/끝에 한정)
구현 복잡도	간단	복잡 (포인터 관리 필요)