Java LinkedList - 직접 구현하기 2

#Java #LinkedList #Foundation #ProjectJF

kiio

— 4 min read

기존에 직접 만든 LinkedList 추가로 특정 위치에 데이터 추가 및 삭제 기능을 만들도록 한다.

void add(int index, Object e)

public void add(int index, Object e) {
    Node newNode = new Node(e);

    if (index == 0) {
        newNode.next = first;
        first = newNode;
    } else {
        Node prevNode = getNode(index-1);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }
    size++;
}
  • 인덱스 통해 데이터 추가
  • 노드 추가에는 프론트와 백 노드도 사이에 추가한다.

Object remove(int index)

public Object remove(int index) {
    Node retNode;
    Object item;
    if (index == 0) {
        retNode = first;
        first = first.next;
    } else {
        Node prevNode = getNode(index-1);
        retNode = prevNode.next;
        prevNode.next = prevNode.next.next;
    }
    item = retNode.item;
    retNode.item = null;
    retNode.next = null;
    size--;
    return item;
}
  • 인덱스 통해 데이터 삭제
  • 노드 삭제에는 프론트와 백 노드 사이에 삭제한다.

add 동작 원리 - 첫 번째 노드 추가

첫 번째 항목으로 노드 추가 하는 과정을 살펴보자.

  • 기존 노드 리스트 : [A->B->C]
    • 첫 번째 노드 D 추가
  • 추가된 노드 리스트: [D->A->B->C]

CLinkedList의 first 변수가 어떻게 노드가 이루어져 있는지 살펴보자.

신규 노드 추가하기 - add

first
+-----+
| x01 |
+--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x01               x02               x03

1. new Node("D")
+----------------+
| item   next    |
| +-----++-----+ |
| | "D" || N/A | |
| +-----++-----+ |
+----------------+
x04

신규 노드 다음 노드 연결하기

first
+-----+
| x01 |
+--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x01               x02               x03

2. x04.next = first
+----------------+
| item   next    |
| +-----++-----+ |
| | "D" || x01 | | 
| +-----++-----+ |
+----------------+
x04

first 멤버 변수 신규 노드로 할당

first
+-----+
| x04 | -> 3. x01 is Replace x04
+--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x01               x02               x03


+----------------+
| item   next    |
| +-----++-----+ |
| | "D" || x01 | | 
| +-----++-----+ |
+----------------+
x04

신규 노드 추가 최종

first
+-----+
| x04 |
+--+--+
   ↓
+--+-------------++----------------++----------------++----------------+
| item   next    || item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "D" || x01 | || | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------++----------------+
x04               x01               x02               x03

add 동작 원리 - 첫 번째 노드 삭제

첫 번째 항목으로 노드 삭제하는 과정을 살펴보자.

  • 기존 노드 리스트 : [D->A->B->C]
    • 첫번 째 노드 D 제거
  • 삭제된 노드 리스트: [A->B->C]

CLinkedList의 first 변수가 어떻게 노드가 이루어져 있는지 살펴보자.

노드 제거 대상

제거 대상: x04 노드
first
+-----+
| x04 |
+--+--+
   ↓
+--+-------------++----------------++----------------++----------------+
| item   next    || item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "D" || x01 | || | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------++----------------+
x04               x01               x02               x03

노드 제거하기 first 변수 교체

first
+-----+
| x01 | 1. x04 is Replcace x01
+--+--+
   ↓ 
+--+-------------++----------------++----------------++----------------+
| item   next    || item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "D" || x01 | || | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------++----------------+
x04               x01               x02               x03

first 멤버 변수 신규 노드로 할당

first
+-----+
| x01 |
+--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x01               x02               x03


2. 
x04.item = null
x04.next = null
+----------------+
| item   next    |
| +-----++-----+ |
| | N/A || N/A | | 
| +-----++-----+ |
+----------------+
x04

신규 노드 추가 최종

first
+-----+
| x01 |
+--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x04               x01               x02               x03

add 동작 원리 - 중간 노드 추가

첫 번째 항목으로 노드 추가 하는 과정을 살펴보자.

  • 기존 노드 리스트 : [A->B->C]
    • 중간에 노드 E 추가
  • 추가된 노드 리스트: [A->B->E->C]

CLinkedList의 first 변수가 어떻게 노드가 이루어져 있는지 살펴보자.

신규 노드 중간에 추가하기 - add

2. prev = first;
first    prev
+-----+  +-----+
| x01 |  | x01 |
+--+--+  +--+--+
   ↓
+--+-------------++----------------++----------------+
| item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------+
x01               x02               x03

1. new Node("E")
+----------------+
| item   next    |
| +-----++-----+ |
| | "E" || N/A | |
| +-----++-----+ |
+----------------+
x04
  • 신규로 추가할 노드를 생성하고, prev 변수를 추가해 first 참조 값을 복사한다.

신규 노드 다음 노드 연결하기

                  3. x02.next = x04(new Node)
                     ↓
+----------------++--+-------------+                  +----------------+
| item   next    || item   next    |                  | item   next    |
| +-----++-----+ || +-----++-----+ |                  | +-----++-----+ |
| | "A" || x02 | || | "B" || x04 | |                  | | "C" || N/A | |
| +-----++-----+ || +-----++-----+ |                  | +-----++-----+ |
+----------------++----------------+                  +----------------+
x01               x02                                 x03

                                    +----------------+
                                    | item   next    |
                                    | +-----++-----+ |
                                    | | "D" || x03 | | 
                                    | +-----++-----+ |
                                    +----------------+
                                    x04

신규 노드 추가 최종

first
+-----+
| x01 |
+--+--+
   ↓
+--+-------------++----------------++----------------++----------------+
| item   next    || item   next    || item   next    || item   next    |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
| | "A" || x02 | || | "B" || x04 | || | "E" || x03 | || | "C" || N/A | |
| +-----++-----+ || +-----++-----+ || +-----++-----+ || +-----++-----+ |
+----------------++----------------++----------------++----------------+
x01               x02               x04               x03

정리

add

  • 노드가 추가된 경우 오른쪽 노드의 인덱스를 한칸 씩 뒤로 이동한다.
    • 연결 리스트는 배열처럼 실제 index가 아니므로 처음 연결된 노드를 index 0, 그다음 노드를 index 1 가정일 뿐, index는 연결된 순서로 뜻한다.
  • 배열리스트 첫 항목에 데이터 추가한 경우 기존 데이터를 오른쪽으로 밀었으나, 연결 리스트는 새로 생성한 노드의 참조만 변경해주면 된다.
  • 연결 리스트의 첫 번째 노드 추가는 매우 빠르다. O(1) 빅오이다.

remove

  • 노드 삭제 시 오른쪽 노드 index 가 앞으로 당겨온다.
  • 배열리스트의 첫 항목이 삭제된 경우 데이터를 왼쪽으로 하나씩 밀었으나, 연결 리스트는 참조만 변경하므로 노드의 변경은 없다.
  • 연결 리스트의 첫 번째 노드 삭제는 매우 빠르다. O(1) 빅오이다.

더 읽어볼 내용