자료구조 / Linked List

Linked List 란?

링크드 리스트는 데이터를 노드로 구성하고 각 노드가 다음 노드를 가리키는 방식으로 이루어진 자료 구조이다. 자바에서는 LinkedList 클래스가 이를 구현한다.

Linked List의 특징

• 각 노드는 데이터와 다음 노드를 가리키는 링크(포인터)로 구성된다.

• 메모리 공간을 유연하게 사용할 수 있어 크기가 동적으로 조절 가능하다.

• 데이터의 삽입과 삭제가 배열에 비해 효율적이다.

Linked List의 장점

• 크기의 동적 조절이 가능하므로 메모리를 효율적으로 사용할 수 있다.
• 삽입, 삭제 연산이 배열에 비해 더 빠르다.

Linked List 사용 예시

import java.util.LinkedList;

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

        // 맨 뒤에 요소 추가
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
		
        // 출력: LinkedList: [1, 2, 3]
        System.out.println("LinkedList: " + linkedList);

        // 맨 앞에 요소 추가
        linkedList.addFirst(0);
        
        // 출력: LinkedList after addFirst: [0, 1, 2, 3]
        System.out.println("LinkedList after addFirst: " + linkedList); 

        // 맨 뒤의 요소 삭제
        linkedList.removeLast();
        
        // 출력: LinkedList after removeLast: [0, 1, 2]
        System.out.println("LinkedList after removeLast: " + linkedList); 

        // 특정 위치에 요소 추가
        linkedList.add(1, 10);
        
        // 출력: LinkedList after add at index 1: [0, 10, 1, 2]
        System.out.println("LinkedList after add at index 1: " + linkedList); 

        // 특정 값으로 요소 삭제
        linkedList.remove(Integer.valueOf(1));
        
        // 출력: LinkedList after remove value 1: [0, 10, 2]
        System.out.println("LinkedList after remove value 1: " + linkedList);
    }
}

단일 LinkedList 구현

이중 LinkedList 구현