LinkedList - 자바 코드 뜯어보기

LinkedList는 Node라는 인스턴스변수를 가지는 자료구조이다.
쉽게 표현하자면 LinkedList는 기차 라는 전체적인 틀 이고, Node는 이 기차의 연결된 열차로 보면 이해하기가 쉽다.
즉, node는 서로 연결되어있는 노드의 위치와, 자신이 가지고 있어야 할 값만을 가지고 있다.

LinkedList의 인스턴스변수 는 대략적으로 이렇게 구성되어있다.
여기서 frist와 last는 말 그대로 노드의 처음과 마지막을 의미하는데, 이 first, last를 기준으로 노드들을 추가,제거,순회한다.

1. 구조

public class LinkedList<E>  
extends AbstractSequentialList<E>  
implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
    transient int size = 0;  

    /**  
    * Pointer to first node.  
    */  
    transient Node<E> first;  

    /**  
    * Pointer to last node.  
    */  
    transient Node<E> last;

LinkedList 내부에 구현되어있는 Node 구현은 다음과 같다.

private static class Node<E> {  
    E item;  
    Node<E> next;  
    Node<E> prev;  

    Node(Node<E> prev, E element, Node<E> next) {  
        this.item = element;  
        this.next = next;  
        this.prev = prev;  
    }  
}

이와같이  next와, prev가 존재하는 노드를 양방향리스트 라고 부른다.

2. add

우리가 처음 LinkedList를 생성하면 다음과 같은 상황이 연출된다.
객체는 초기화가 되므로 선언만 되었던 변수들이 각자 초기화가 되면서 0, null을 할당한다.

여기서 다음과 같이 값을 추가하면,

linkedList.add("firstValue");

다음과 같은 코드가 호출된다.
linkLast 메서드를 5단계로 분류했다.

public boolean add(E e) {  
    linkLast(e);  
    return true;  
}

void linkLast(E e) {  
    final Node<E> l = last;  //1
    final Node<E> newNode = new Node<>(l, e, null);  //2
    last = newNode;  //3
    if (l == null)  
    	first = newNode;  	
    else  
        l.next = newNode;  
    size++;  //4
    modCount++;  //5
}

이 부분은 현재 last노드를 임시로 비교하고자 변수로 선언한다. 

final Node<E> l = last; //1

그리고 다음과 같이 새 노드를 생성한다.

final Node<E> newNode = new Node<>(l, e, null); //2

시각적으로 표현하면 다음과 같다.
최초 삽입 시에는 last도 null이므로 결국 prev = null이 된다.

여기서는 linkdList의 last를 직접적으로 newNode로 지정한다.
만약 
inkedList에 아무런 데이터도 없을 때에는 newNode를 최초,최후 노드로 지정한다.
그렇지 않다면,
기존에 데이터가 있던 상황이라면, l.next, 즉 마지막 노드의 다음 노드로 newNode를 지정한다.

last = newNode;  //3
if (l == null)  
	first = newNode;  
else  
	l.next = newNode;

단순하게 시각화 한다면 다음과 같다

최초 노드 삽입 시

기존 노드에 추가적으로 삽입 시(size=1)

이제 linkdList에 newNode가 추가되었으니, size를 증가시켜준다.

size++;  //4

그런데 이상한점을 발견한다. 분명, modCount는 인스턴스 변수에 없었는데, 어디서 나타난걸까?

modCount++;  //5

modCount는 AbstractList로 구현된 것이고, LinkedList는 이를 계승 했기 때문에 가능하다. 

 

modCount는 수정된 횟수를 추적하는데 이것은 Iterator를 위해 사용된다.
Iterator는 조회의 역할을 위해 사용하므로 순회 중 데이터 변경이 감지되면,
즉 modCount의 변경이 감지되면 예외를 발생 시켜서 
데이터 무결성을 방지하는 역할이라고 이해하고 있다.

3. remove 

이번에는 제거 로직을 알아보자.

LinkedList<String> linkedList = new LinkedList<>();  
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");

 remove를 호출하면

linkedList.remove("firstValue");

LinkedList는 null도 데이터로 취급하기에 null인 경우와 아닌 경우를 나누어서 제거한다. 

public boolean remove(Object o) {  
    if (o == null) {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}

E unlink(Node<E> x) {  
    // assert x != null;  
    final E element = x.item;  //1
    final Node<E> next = x.next;  
    final Node<E> prev = x.prev;  

    if (prev == null) {  //2
        first = next;  
    } else {  
        prev.next = next;  
        x.prev = null;  
    }  

    if (next == null) {  //3
    	last = prev;  
    } else {  
        next.prev = prev;  
        x.next = null;  
    }  

    x.item = null;  
    size--;  
    modCount++;  
    return element;  
}

remove에서 값(item)이 일치하는 Node를 찾아 unlink에게 전달한다.
제시한 예시의 경우, prev = null, next = xxx222가 할당된다.

final E element = x.item;  //1
final Node<E> next = x.next;  //xxx222
final Node<E> prev = x.prev;  //null

만약 
prev=null 즉, 현재 노드가 제일 앞의 노드라면 
linkedList의 first는 현재 노드의 next(다음 노드)가 된다.

 

if (prev == null) {  //2
	first = next;  
} else {  
    prev.next = next;  
    x.prev = null;  
}

근데 이해가 가지 않는 부분이 존재했다.
first = next 이전에, next.prev를 null처리 하지 않는 이유는 뭘까?

이해가 잘 가지 않아 스텍오버플로우에 질문했다.

[data structures - Why is next.prev not explicitly set to null in Java LinkedList's unlink method when removing the first node? - Stack Overflow](https://stackoverflow.com/questions/77703595/why-is-next-prev-not-explicitly-set-to-null-in-java-linkedlists-unlink-method-w?noredirect=1#comment136988909_77703595)

 

이유는 매우 간단했다.
next가 null아닐때의 로직을 보면, 
next.prev = prev로 설정하는것을 볼 수 있다.
즉, x의 prev = null 이므로, next.prev= null이 되고,
x.next = null로 설정하므로 GC가 동작하게 된다.

if (next == null) {  //3
	last = prev;  
} else {  
    next.prev = prev;  
    x.next = null;  
}

이렇게 보면 next.prev = null 처리가 진행된다.

이렇게 되면 GC가 동작하여 노드가 성공적으로 제거된다.

 

추가적으로, remove는 위에서 말했듯이, null인지 아닌지 여부를 먼저 판단하고 진행한다. 

그래서 이런식으로 null에 대한 참조변수가 다르거나, null을 직접 넣어도

동일하게 순회시 발견되는 첫번째 null만 제거한다.

String nullValue = null;
String nullValue2 = null;
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("firstValue");
linkedList.add(nullValue);
linkedList.add(nullValue);
System.out.println("linkedList = " + linkedList);

linkedList.remove("firstValue");
System.out.println("linkedList = " + linkedList);

linkedList.remove(nullValue2);
System.out.println("linkedList = " + linkedList);

linkedList.remove(null);
System.out.println("linkedList = " + linkedList);
System.out.println("linkedList.size() = " + linkedList.size());

 

linkedList = [firstValue, null, null]
linkedList = [null, null]
linkedList = [null]
linkedList = []
linkedList.size() = 0

Why is next.prev not explicitly set to null in Java LinkedList's unlink method when removing the first node?