[선형 데이터 구조] LinkedList

LinkedList

자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하여 메서드로 이리저리 조작이 가능하게 만든 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 참조함으로써 이어지는 구조이다.

단방향 연결 리스트 (singly linked list)

위 그림을 보면 LinkedList는 각기 노드마다 화살표로 연결되어 리스트 형태로 나열되어 있는 것을 볼 수 있다. 여기서 노드는 하나의 객체라고 보면된다. 즉, 객체를 만들면 객체의 주소가 생기게 되는데, 노드마다 각기 객체의 주소를 서로 참조함으로서 연결 형태를 구성하는 것이다.

단일 노드를 그림과 코드로 표현한다면 다음과 같이 될 것이다.

단방향 연결 리스트 (singly linked list) Node 구조

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

 

LinkedList 종류

단방향 연결 리스트 (singly linked list)

단방향 연결 리스트 (singly linked list)

위에서 보았듯이, 다음 노드를 가리키기 위한 포인터 필드 next만을 가지고 있는 링크드 리스트를 singly linked list라고 한다. 하지만 단일 연결 리스트는 현재 요소에서 이전 요소로 접근해야 할때 매우 부적합한 특징이 있다.

예를들어 LinkedList에 저장된 데이터가 10000개라면 9999 번째 데이터에 접근하려면 Node를 9999번 이동해야 하기 때문이다. 이를 극복한 것이 doubly linked list 구조 이다.

 

양방향 연결 리스트 (doubly linked list)

양방향 연결 리스트 (doubly linked list)

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    Node prev; // 이전 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};

기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드 prev가 추가된 형태를 doubly linked list라고 부른다.

 

singly linked list는 이동 방향이 단방향이기 때문에, 이를 보완하여 역순으로도 검색이 가능하도록 한 것이다. 따라서 doubly linked list는 singly linked list보다 각 요소에 대한 접근과 이동이 쉽기 때문에 기본적으로 많이 사용된다.

 

Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 doubly linked list로 구현 되어 있다.

 

양방향 원형 연결 리스트 (doubly circular linked list)

양방향 원형 연결 리스트 (doubly circular linked list)

추가로 doubly linked list 보다 접근성이 더 개선된 doubly circular linked list도 있다. 단순히 첫번째 노드와 마지막 노드를 각각 연결시켜, 마치 원형 리스트 처럼 만들었다고 보면 된다.

 

단일 연결 리스트를 원형으로 연결한 singly circular linked list도 있지만 잘 쓰이지 않는다.

 

이러한 구조는 티비 채널을 순회하거나 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다고 보면 된다.

 

※LinkedList의 get()

LinkedList는 배열이 아닌데도 인덱스로 데이터에 접근할 수 있다.

LinkedList는 '노드'들이 이어진 구조이다. 인덱스 값을 따로 저장하는것이 아니라 get(index) 같은 메서드를 호출하면, head(첫 노드)부터 next를 따라가면서 index번 이동해서 찾는다.

그래서 list.get(1)처럼 인덱스로 접근할 때 맨 앞 노드부터 순차적으로 이동해야하기 때문에 읽기 시간 복잡도는 O(N) 이다. 즉, 데이터에 접근할 때는 LinkedList는 ArrayList처럼 빠르지는 않다.

그래서 많은 인덱스 접근이 필요하면 ArrayList가 적합하고, 중간에 삽입/삭제가 많으면 LinkedList가 적합하다.

상황	ArrayList	LinkedList
맨 뒤 삽입	빠름 (O(1))	빠름 (O(1))
맨 뒤 삭제	빠름 (O(1))	빠름 (O(1))
중간 삽입/삭제	느림 (O(N))	위치 탐색: O(N) / 삽입/삭제 자체: O(1)
인덱스 접근	빠름 (O(1))	느림 (O(N))

 

LinkedList 사용법

import java.util.LinkedList;

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

        // 2. 요소 추가 (맨 뒤에 추가)
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 3. 특정 위치에 요소 추가
        list.add(1, "Blueberry"); // 인덱스 1 위치에 삽입

        // 4. 요소 꺼내기 (인덱스로 접근)
        String fruit = list.get(2);

        // 5. 요소 수정
        list.set(2, "Coconut"); // 2번 인덱스 수정

        // 6. 요소 삭제
        list.remove(1); // 인덱스 1의 요소 삭제

        // 7. 리스트 크기 확인
        int size = list.size();

        // 8. 리스트 비우기
        list.clear();
    }
}

 

참고자료

[1] [Inpa Dev 👨‍💻:티스토리] - JAVA☕LinkedList 구조 사용법 완벽 정복하기

🧱 자바 LinkedList 구조 & 사용법 - 정복하기