[자료구조] 01. 배열 리스트(ArrayList)와 연결 리스트(LinkedList)

전체 코드

https://github.com/ahn-sj/java-custom-box/tree/main/src/main/java/ohdodok/custom/collections/list

GitHub - ahn-sj/java-custom-box: Implementing a Java embedded API. I want to know the operating principles of Java in detail.

 

---

 

배열 리스트(ArrayList)

 

배열 리스트는 일반 배열과 동일하게 연속된 메모리를 사용하여 크기가 가변적인 선형 리스트이다.
get() 기준 시간복잡도 O(1)

 

이미지 출처:https://www.scaler.com/topics/java/arraylist-in-java/

 

 

 

ArrayList를 구현하면서 초기 capacity의 값 설정을 이해하는데 어려움이 있었다.
https://github.com/ahn-sj/java-custom-box/issues/5

ArrayList의 initialCapacity에 대해 알아본다. · Issue #5 · ahn-sj/java-custom-box

 

공식 문서에 의하면 매개변수에 값을 주지 않은 경우 초기 capacity의 값이 10으로 설정된다고 하는데 실제로 기본 생성자가 동작되는 코드로 가면 Object[] elementData = {}로 설정되도록 되어있었다.

 

그러나 ArrayList 클래스의 녹색을 차근히 읽어본 결과 첫 번째 요소가 추가될 때 DEFAULT_CAPACITY(= 10)으로 추가되는 것을 알게 되었다.

The array buffer into which the elements of the ArrayList are stored.
The capacity of the ArrayList is the length of this array buffer.
Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.

 

번역을 하면 첫 번째 요소가 추가될 때 elementData의 DEFAULTCAPACITY_EMPTY_ELEMENTDATA(= { })과 같은 경우 DEFAULT_CAPACITY(= 10)만큼 확장된다고 한다.

 

 

 

---

 

연결 리스트(LinkedList)

 

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.
get() 기준 시간복잡도 (n)

이미지 출처:https://opentutorials.org/module/1335/8857

 

연결 리스트는 기본적으로 노드(Node)라는 구조체를 기본으로 한다. 그리고 이 노드는 데이터를 담는 칸과 다음 노드의 주소를 가리키는 칸으로 이루어져 있다.

public static class Node {
    private Object data;
    private Node next;

    public Node(Object data) {
        this.data = data;
        this.next = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

이러한 구조 때문에 연결 리스트는 다음과 같은 특징을 갖는다.

1. 데이터의 이동 없이 중간에 삽입/삭제가 가능하다.
2. 랜덤 액세스가 불가능하다.
3. Head의 주소는 반드시 기억해야 한다.

 

이제 LinkedList의 연산에 대해서 알아보자.

 

1. 삽입 연산

기존 배열 리스트와는 다르게 데이터 삽입시에 원하는 위치보다 한 칸 앞의 노드의 주소 값을 새로운 노드의 주소 값으로 변경한다. 이러한 연산 때문에 배열 리스트에 비해 매우 유연하게 연산을 수행할 수 있다.

public void add(Node node) {
    Node tempNode = head;

    if(head == null) {
        head = node;
    } else {
        for (int i = 1; i < size; i++) {
            tempNode = tempNode.next;
        }
        tempNode.next = node;
    }
    size++;
}

 

2. 삭제 연산
기존 배열 리스트와 다르게 이전 원소들을 전부 옮겨 담을 필요없이 삭제하기를 원하는 노드의 앞 노드와 뒤 노드를 이어주고, 원하는 노드를 메모리에서 해제해주면 된다.

public void remove(int index) {
    Node tempNode = head;

    for (int i = 0; i < index - 1; i++) {
        tempNode = tempNode.next;
    }
    tempNode.next = tempNode.next.next;
    size--;
}

 

3. 탐색 연산
데이터들이 모두 떨어져서 저장되어있기 때문에 랜덤 액세스를 할 수 없다. 때문에 n번째 원소를 찾으려면 n번의 루프를 돌아야 한다. 이러한 이유때문에 연결 리스트의 시간 복잡도는 O(n)이다.

public void printAll() {
    Node tempNode = head;
    System.out.println("head   = " + tempNode);

    for (int i = 1; i < size; i++) {
        tempNode = tempNode.next;

        System.out.println("Node " + i + " = " + tempNode);
    }
}

public String get(int index) {
    Node tempNode = head;

    for (int i = 0; i < index; i++) {
        tempNode = tempNode.next;
    }
    return tempNode.toString();
}

 

 

[실행 결과]

 

class CustomLinkedListTest {

    @Test
    @DisplayName("LinkedList")
    public void simple_linkedList() throws Exception {
        // given
        CustomLinkedList linkedList = new CustomLinkedList();

        linkedList.add(new Node("강낭콩"));
        linkedList.add(new Node("검은콩"));
        linkedList.add(new Node("땅콩"));
        linkedList.add(new Node("머리콩"));

        // when & then
        linkedList.printAll();
        System.out.println("=================");

        System.out.println(linkedList.get(2));
        System.out.println("=================");

        linkedList.remove(2);
        linkedList.printAll();
    }
}

head   = Node{data=강낭콩}
Node 1 = Node{data=검은콩}
Node 2 = Node{data=땅콩}
Node 3 = Node{data=머리콩}
=================
Node{data=땅콩}
=================
head   = Node{data=강낭콩}
Node 1 = Node{data=검은콩}
Node 2 = Node{data=머리콩}

 

 

참고

https://gusdnd852.tistory.com/100

리스트 (3) - 연결리스트 (Linked List)