[자료구조/Java] LinkedList - 조회/추가/삭제 코드구현

이전에 정적배열 Array와 동적배열 ArrayList에 대해 알아보았습니다. 이번에는 또 다른 동적배열인 LinkedList에 대해 알아보겠습니다.

 

LinkedList 링크드리스트

LinkedList는 Node를 기반으로 구성된 자료구조를 말하며, ArrayList와 마찬가지로 List클래스를 기반으로 합니다. Node는 Data를 담을 수 있는 변수와 다른 Node를 참조하는 2개의 변수로 이루어져있습니다.

 

LinkedList는 Node의 구성에 따라 싱글 링크드리스트(Single-LinkedList), 더블 링크드리스트(Double-LinkedList)로 구분할 수 있습니다.

• Single Linked List
• Double Linked List

 

 

Single Linked List

Single LinkedList의 노드

public class Node<T> {
    public T data;
    Node<T> next = null;
}

싱글 링크드리스트(Single LinkedList)는 각 노드가 다음 노드를 가르키는 형태로 구성됩니다.

싱글 링크드리스트의 단점은 리스트를 순회할 때, 이전의 노드로 이동할 수 없기때문에 단방향으로만 순회가 가능합니다. 이를 보완하기 위해서 고안된 것이 아래에 소개될 더블 링크드리스트입니다.

 

 

 

 

 

Double LinkedList의 Node

Double LinkedList의 노드

public class Node<T> {
    public T data;
    Node<T> prev = null;
    Node<T> next = null;
}

더블 링크드리스트는 Node 내의 2개의 참조 변수가 이전과 다음 Node를 가리키게 되어있습니다. 마치 체인처럼 서로 연결되어 있는 형식이죠. 가장 처음과 끝 노드는 head, tail이라고 부릅니다.

 

 

LinkedList의 조회

public Node<T> search(T data){
    Node<T> cursor = this.head;
    while(cursor.data != data) {
        if(cursor.next == null) {
            System.out.println("search result: "+data+ " does not exist");
            return null;
        }
        cursor = cursor.next;
    }
    return cursor;
}

 

 

LinkedList의 추가

LinkedList에 노드를 추가하기 위해서는 다음과 같은 순서를 따릅니다.

1. 삽입하고자 하는 Node의 prev_node를 이전 노드를 참조하게 한다.
2. 삽입하고자 하는 Node의 next_node를 다음 노드를 참조하게 한다.
3. prev_node의 next_node를 삽입하고자 하는 Node를 참조하게 한다.
4. next_node의 prev_node를 삽입하고자 하는 Node를 참조하게 한다.

 

특정 데이터 뒤에 새로운 데이터를 삽입하는 경우

// target데이터 노드 뒤에 새로운 데이터 노드 삽입
public void addNode(T newData, T target){
    if(this.head == null) {
        System.out.println("List is empty");
    } else {
        Node<T> cursor = this.search(target);
        if(cursor.next == null) {
            this.addNode(newData);
        } else {
            Node<T> newNode = new Node<T>(newData);
            newNode.prev = cursor;
            newNode.next = cursor.next;
            cursor.next.prev = newNode;
            cursor.next = newNode;
        }
    }
}

 

LinkedList의 가장 마지막에 데이터를 삽입하는 경우

// LinkedList의 마지막에 데이터 추가하기
public void addNode(T data){
    if(this.head == null) {
        this.head = new Node<T>(data);
        this.tail = this.head;
    } else {
        Node cursor = this.tail;
        cursor.next = new Node<T>(data);
        cursor.next.prev = cursor;
        this.tail = cursor.next;
    }
}

 

 

 

LinkedList의 Node 삭제

LinkedList에 기존의 데이터를 삭제하기 위해서는 다음과 같은 순서를 따릅니다.

1. 삭제되는 Node의 next_node의 prev_node를, 삭제되는 Node의 prev_node를 참조하게 한다.
2. 삭제되는 Node의 prev_node의 next_node를, 삭제되는 Node의 next_node를 참조하게 한다.
3. 삭제되어야 하는 Node를 삭제한다.

// 특정 값을 지닌 노드 삭제. 해당 노드가 존재하지 않으면 false, 삭제성공 시 true 반환
public boolean delNode(T data) {
    if(this.head == null) {
        System.out.println("list is empty");
        return false;
    }

    if(this.head.data == data) {
        this.head = this.head.next;
        this.head.prev = null;
        return true;
    }

    Node<T> cursor = this.search(data);
    if(cursor.next == null) {
        cursor.prev.next = null;
        cursor.prev = null;
        return true;
    }
    cursor.prev.next = cursor.next;
    cursor.next.prev = cursor.prev;
    return true;
}

전체 코드는 개인 깃허브(이곳)에서 확인가능합니다.