LinkedList

LinkedList를 구현하는 방법에는 여러가지가 있는데 하나씩 살펴보겠습니다.

 

연결 리스트 종류

단일 연결 리스트 (Single Linked List)

• 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.
• 마지막 노드는 null 을 가리킵니다.
• 단방향이기 때문에 주로 앞에서 부터 순회합니다. 
• 구현이 간단하지만 뒤에서 앞으로의 이동은 불가능 합니다.

이중 연결 리스트 (Double Linked List)

• 각 노드가 데이터와 이전, 다음 노드를 가리키는 포인터로 구성됩니다.
• 앞, 뒤로의 이동이 자유롭게 가능하며 역순회도 간단합니다.
• 두개의 포인터를 갖기 때문에 메모리 공간이 더 필요합니다.
• 데이터 추가나 삭제시에 이전 노드와 다음 노드 모두의 참조를 업데이트하는 추가 작업이 필요합니다.

원형 연결 리스트 (Circular Linked List)

• 단일 연결 리스트나 이중 연결 리스트의 변형입니다.
• 마지막 노드가 첫번째 노드를 가리킵니다.
• 순환적인 구조를 가지며, 특정한 상황에서 유용하게 사용됩니다. (ex: 순환 큐)
• 종료 조건을 설정하는 것이 복잡하다.
  (순회 중 언제 리스트가 끝나는지 판별 하기가 어려울 수 있다.)

다중 연결 리스트 (Multi Linked List)

• 두 개 이상의 포인터 또는 참조를 가진 노드로 구성된 리스트입니다.
• 복잡한 구조나 다양한 토폴로지를 표현할 때 사용됩니다.

 

구현

아래 인터페이스를 정의하여 단일 연결 리스트를 구현해 보려고한다.

주요 로직이 들어가는 삽입, 삭제, 검색에 대한 로직을 살펴보자.

 

public interface LinkedList<E> {
    void add(E item); // list의 마지막에 삽입
    void add(E item, int index); // index 위치에 삽입
    int size(); // list의 사이즈 확인
    void clear(); // list 초기화
    E get(int index); // index의 node 값 반환
    void remove(); // list의 마지막 node 삭제
    void remove(int index); // index 위치의 node 삭제
    void remove(E item); // 해당 값을 가지는 node 삭제
    int indexOf(E item); // 해당 값을 가지는 node의 index 반환
    boolean contains(E item); // 해당 값을 가지는지 확인
}

 

생성자

SingleLinkedList 는 first , last 노드와 리스트 size 를 변수로 갖는다.

Node 는 단일 연결 리스트로, 노드의 값과 다음 노드에 대한 정보를 갖는다.

first 와 last 는 조회, 삽입, 삭제 시 시간을 줄이기 위해 갖고 있는 정보이다.

public class SingleLinkedList<E> implements LinkedList<E> {
    private Node<E> first;
    private Node<E> last;
    private int size;

    private static class Node<E> {
        E item;
        Node<E> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

 

초기화

생성자를 통해 SingleLinkedList 를 초기화 해준다.

public SingleLinkedList() {
    clear();
}

@Override
public void clear() {
    first = null;
    last = null;
    size = 0;
}

 

First Node, Last Node

first 와 last Node는 아래와 같이 적용된다.

1. 빈 List 인 경우 둘다 null 인 상태이다.
2. 하나의 Node가 추가된 경우 해당 Node는 first 이자 last Node 이다.
3. 이후 Node의 추가, 제거 연산에 따라 first 와 last Node를 할당한다.

자세한 방식은 삽입 삭제 연산에서 다뤄보자.

Find Node

삽입, 삭제, 검색 연산을 알아보기 전에 공통적으로 사용한 Node를 찾는 method 부터 알아보자.

• 연산 시간을 줄이기 위해 찾고자 하는 index 가 size - 1 과 같다면 last  Node를 반환한다.
• 그렇지 않다면 first Node 부터 index 만큼 카운트하여 node를 찾는다.

private Node<E> node(int index) {
    if (index == size - 1) {
        return last;
    }

    Node<E> node = first;
    while (index-- > 0) {
        node = node.next;
    }
    return node;
}

 

Add Node

Node를 추가할 때 Node들의 연결관계를 어떻게 정리할지 알아보자.

 

List의 가장 앞 부분에 Node를 추가하는 경우 새로운 Node가 first 가 되며 기존 first Node를 새로운 Node의 next 로 연결시켜 준다.

 

 

List의 중간에서 Node를 추가하는 경우 기존 index의 Node를 새로운 Node의 next 로 연결시켜 주고 기존 이전 Node의 next 를 새로운 Node에 연결시켜 준다.

 

 

List의 가장 끝에 Node를 추가하는 경우 가장 마지막 Node의 next 에 새로운 Node를 연결시켜 주고 새로운 Node는 last 가 된다.

 

• add(E item) 
• List의 끝부분에 Node를 추가한다.
• size 가 0인 경우 first 에도 새로운 Node를 할당하기 위해 linkFirst 를 사용한다.
• 그렇지 않은 경우 last Node 뒤에 연결시켜 준다.

• add(E item, int index) 
• 메서드는 List의 특정 index  위치에 Node를 추가한다.
• checkPosition(index) 를 통해 index가 List의 범위 내인지 체크한다.
• index가 0인 경우 first 에 할당하기 위해 linkFirst 를 사용한다.
• 그렇지 않은 경우 index - 1 위치 Node 뒤에 연결시켜 준다.
  index</code >  위치에 Node를 추가하기 위해선 index - 1 Node 뒤에 연결시켜야 한다.

 

@Override
public void add(E item) {
    if (size == 0) {
        linkFirst(item);
    } else {
        linkAfter(item, last);
    }
}

@Override
public void add(E item, int index) {
    checkPosition(index);

    if (index == 0) {
        linkFirst(item);
    } else {
        linkAfter(item, node(index - 1));
    }
}

 

• linkFirst(E item) 
• List의 첫 부분을 설정한다.
• 기존 first 를 새로운 Node 뒤에 연결시켜 준다.
• 새로운 Node는 first 가 된다.
• 만약 새로운 Node에 연결된 Node(즉, 기존 first )가 null 이라면,
  현재 리스트는 비어있는 상태였으므로 last 에도 할당해 준다.
• size 를 증가시킨다.
• linkAfter(E item, Node<E> node)</code > 

• 인자로 받아온 Node에 연결되어 있던 Node를 새로운 Node 뒤에 연결시켜 준다.
• 인자로 받아온 Node 뒤에 새로운 Node를 연결시켜 준다.
• 만약 새로운 Node에 연결된 Node(즉, 인자로 받아온 Node에 연결되어 있었던)가 null 이라면,
  해당 Node는 마지막 Node로 last 에도 할당해 준다.
• size 를 증가시킨다.

private void linkFirst(E item) {
    Node<E> prevFirst = first;
    Node<E> newNode = new Node<>(item, prevFirst);
    first = newNode;

    if (newNode.next == null) {
        last = newNode;
    }
    size++;
}

private void linkAfter(E item, Node<E> node) {
    Node<E> prevNext = node.next;
    Node<E> newNode = new Node<>(item, prevNext);
    node.next = newNode;

    if (newNode.next == null) {
        last = newNode;
    }
    size++;
}

 

Remove Node

Node를 삭제할 때 Node들의 연결관계를 어떻게 정리할지 알아보자.

 

List의 첫번째 Node를 제거하는 경우 첫번째 Node에 연결된 Node를 first 에 할당해 주면 된다.

참조되지 않는 Node는 GC 대상이된다.

 

List의 중간에서 Node를 제거하는 경우 기존 Node의 연결 노드를 이전 노드에 연결시켜준다.

참조되지 않는 Node는 GC</code > 대상이된다.

 

 

List의 마지막 Node를 제거하는 경우 마지막 이전 Node를 last</code > 에 할당하고 연결을 끊어준다.


참조되지 않는 Node는 GC</code > 대상이된다.

 

• remove() 
• 해당 메서드는 List의 마지막을 삭제하는 메서드이다.
• unlinkLast() 를 호출해 준다.
• remove(int index) 
• first 와 last Node의 삭제는 위치를 알고 있기 때문에 간단히 수행할 수 있다.
• index 위치가 first , last 인지 먼저 확인하여 unlinkFirst() , unlinkLast() 를 호출한다.
• 이외의 경우 검색한 Node를 통해 unlink(Node<E> node)</code > 를 호출한다.

• remove(E e) 

• 인자로 받아온 데이터를 통해 index 를 검색한다.
• index 를 가지고 remove(int index) 를 호출한다.

@Override
public void remove() {
    unlinkLast();
}

@Override
public void remove(int index) {
    Node<E> node = node(index);
    if (node == first) {
        unlinkFirst();
    } else if (node == last) {
        unlinkLast();
    } else {
        unlink(node);
    }
}

@Override
public void remove(E e) {
    remove(indexOf(e));
}

 

• unlinkFirst() 
• List의 첫 번째 Node를 제거한다.
• first == last 인 경우 List에 Node가 하나만 존재하는 것으로 clear() 를 통해 초기화 시켜준다.
• 아닌 경우 첫 번째 Node에 연결된 Node를 first 에 할당한다.
• size 를 감소시킨다.
• unlinkLast() 
• List의 마지막 Node를 제거한다.
• first == last 인 경우 List에 Node가 하나만 존재하는 것으로 clear()</code > 를 통해 초기화 시켜준다.
• 단일 연결 리스트이기 때문에 first Node 부터 시작하여 last 에 연결된 Node를 찾는다.
• 해당 Node를 last 로 할당하고 연결을 해제한다.
• size 를 감소시킨다.
• unlink(Node<E> node) 
• List의 특정 Node를 삭제한다.
• 단일 연결 리스트이기 때문에 first</code > Node 부터 시작하여 인자로 받은 Node 에 연결된 Node를 찾는다.
• 인자로 받은 Node의 이전 노드와 다음 노드를 연결시켜 준다.
• size 를 감소시킨다.

 

private void unlinkFirst() {
    if (first == last) {
        clear();
    } else {
        first = first.next;
        size--;
    }
}

private void unlinkLast() {
    if (first == last) {
        clear();
    } else {
        Node<E> prevNode = first;
        while (prevNode.next != last) {
            prevNode = prevNode.next;
        }
        last = prevNode;
        last.next = null;
        size--;
    }
}

private void unlink(Node<E> node) {
    Node<E> prevNode = first;
    while (prevNode.next != null && prevNode.next != node) {
        prevNode = prevNode.next;
    }
    prevNode.next = node.next;
    size--;
}

 

테스트

public static void main(String[] args) {
    SingleLinkedList<String> list = new SingleLinkedList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    System.out.println(list + ", size: " + list.size());

    list.add("4", 0);
    list.add("5", 0);
    System.out.println(list + ", size: " + list.size());

    list.add("6", 4);
    list.add("7", 5);
    System.out.println(list + ", size: " + list.size());

    list.remove(2);
    list.remove();
    System.out.println(list + ", size: " + list.size());
}
// [1, 2, 3], size: 3
// [5, 4, 1, 2, 3], size: 5
// [5, 4, 1, 2, 6, 7, 3], size: 7
// [5, 4, 2, 6, 7], size: 5