링크드리스트(Linked List) 구현 Java

링크드리스트란?

데이터가 연속한 공간에 저장되는것이 아닌, 데이터와 다음 데이터로의 링크를 가진 노드들이 연결된 선형 데이터구조 

링크드리스트 구조

public class LinkedList {
    
    Node head;
}
 
public class Node {
    
    Node next;
    String data;
    
    public Node(String data) {
        this.data = data;
    }
    
}

링크드리스트 장단점

장점

배열처럼 처음부터 크기가 고정되는게 아니라 동적할당을 하기 때문에 선언시 크기를 지정하지 않아도 되어 메모리를 효율적으로 사용할 수 있다.

데이터의 추가/삭제가 용이하다.

단점

배열은 데이터를 찾을 때 인덱스로 접근하고 링크드리스트는 처음부터 순차적으로 접근한다. 그래서 k번째 데이터를 조작할 때 시간이 O(n)으로 오래 걸린다.

링크드리스트 구현

링크드리스트의 오퍼레이션들을 직접 구현해보자. 먼저 아래와 같은 링크드리스트 맨 앞에 데이터를 삽입하는것을 생각해보자.

순서는 다음과 같을 것이다.

1 노드 생성

2 1에서 만든 노드의 링크를 기존 링크드리스트의 head로 연결

3 링크드리스트의 head를 1에서 만든 노드로 변경

그림으로 보면 이해가 더 쉽다.

코드로 구현하면 다음과 같다.

public void addFirst(String data) {
    if(head == null) {
        head = new Node(data);
        return;
    }
    Node newHead = new Node(data);
    newHead.next = head;
    head = newHead;
}

이번엔 링크드리스트의 마지막 값을 삭제해보자.

1 현재노드를 링크드리스트의 head로 지정

2 현재노드를 다음노드로 변경

3 다음노드를 가리키는 링크가 없을때까지 2를 반복

4 현재노드의 이전노드의 링크 삭제

previous : 이전노드 / current : 현재노드

public void removeLast() {
    if(head == null) {
        return;
    }
    if(head.next == null) {
        head = null;
        return;
    }
    Node current = head;
    Node previous = null;
    while(current.next != null) {
        previous = current;
    }
    current = current.next;
    previous.next = null;
}

처음값 삭제, 특정 값 삭제 등도 구현해보자.

public class LinkedList {
    
    Node head;
    
    public void addFirst(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node newHead = new Node(data);
        newHead.next = head;
        head = newHead;
    }
    
    public void addLast(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }
    
    public void removeFirst() {
        if(head == null) {
            return;
        }
        head = head.next;
    }
    
    public void removeLast() {
        if(head == null) {
            return;
        }
        if(head.next == null) {
            head = null;
            return;
        }
        Node current = head;
        Node previous = null;
        while(current.next != null) {
            previous = current;
        }
        current = current.next;
        previous.next = null;
    }
    
    public void removeValue(String data) {
        if(head == null) {
            return;
        }
        if(head.data.equals(data)) {
            head = head.next;
            return;
        }
        Node current = head;
        while(current.next != null) {
            if(current.next.data.equals(data)) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
}