연결리스트(LinkedList)

연결리스트(LinkedList)

LinkedList는 자바에서 제공하는 자료구조 중 하나로, 리스트를 구현하는데 사용된다. LinkedList는 노드(Node)들이 링크로 연결되어 있는 자료구조이다. 

 

각 노드는 데이터와 다음 노드를 가리키는 포인터(주소)로 이루어져 있다. 첫 번째 노드를 head(머리)라고 하고, 마지막 노드는 tail(꼬리)라고 한다.

새로운 노드가 추가되면, 추가된 노드의 포인터가 다음 노드를 가리키도록 설정되고, 이전 노드의 포인터는 새로운 노드를 가리키도록 변경된다. 

노드가 삭제가 되면, 삭제 되는 노드의 이전 노드의 포인터를 삭제 하고 삭제 대상 노드의 다음 노드로 포인트를 지정 후 삭제된다. 삭제는 GC(가비지 컬렉터)가 참조되지 않는 데이터에 관해서 알아서 삭제 해준다. (따로 구현 x)

 

장점

• 데이터의 공간을 미리 할당할 필요가 없다. 

배열 자료구조의 경우 한번 할당한 사이즈를 변경 할 수 없다는 것을 생각하면 이것이 왜 장점인지 알 수 있다. 

 

• 삽입과 삭제를 위해서는 포인터만 변경해주면 되기 때문에 삽입과 삭제가 빠르다.

 

단점

• 검색과 접근을 위해서는 첫 번째 노드부터 순서대로 접근해야 하기 때문에 검색과 접근에는 불리하다.

LinkedList는 각 요소(Node)가 이전 요소와 다음 요소의 주소를 가지고 연결된 구조이기 때문에 LinkedList는 ArrayList와는 다르게 인덱스(index)를 사용하여 요소에 접근할 수 없다. 즉, 요소에 접근하기 위해서는 첫 번째 노드부터 순서대로 탐색해야 한다. 

 

• 연결 정보를 위한 별도 데이터 공간이 필요로 한다. 
• 데이터 추가, 삭제 시 앞뒤 데이터의 연결 재구성하는 작업이 필요로 하다.

---

양방향 연결 리스트(Doubly Linked List)

양방향 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 포인터를 가지는 연결 리스트이다. 이전 노드를 가리키는 포인터는 'prev'라는 이름으로, 다음 노드를 가리키는 포인터는 'next'라는 이름으로 표현이 된다.

 

양방향 연결 리스트도 단방향과 같이 첫 번째 노드를 가리키는 'head'와 마지막 노드를 가리키는 'tail' 포인터가 존재한다. head에 있는 노드의 경우, 제일 앞에 있는 노드이기 때문에 prev 포인트는 null 값을 가지게 된다. tail의 경우, 마지막을 뜻 하기 때문에 next 포인터가 null 이다. 

 

장점

• 양방향 연결 리스트는 단방향 연결 리스트와 달리 양방향으로 탐색이 가능하다. (특정 노드에서부터 앞이나 뒤로 탐색하는 것도 가능)
• 양방향 연결 리스트는 노드를 삭제 할 때 연결이 끊어진 이전 노드와 다음 노드를 참조하는 포인터만 수정하면 되므로 단방향 연결 리스트보다 삭제 연산이 효율적이다.

 

단점

• 단방향 연결 리스트보다 각 노드가 더 많은 메모리를 사용하므로 메모리 사용량이 증가함. 
• 연결 리스트의 맨 앞이나 맨 끝에서 삽입이나 삭제가 일어날 경우, head 또는 tail 포인터를 조작해야 하므로 이 작업이 상대적으로 더 복잡할 수 있다.

---

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

원형 연결 리스트는 일반적인 연결 리스트와 유사하지만, 마지막 노드가 첫 번째 노드와 연결되어 있는 자료구조이다. 즉, 리스트의 마지막 노드가 첫 번째 노드를 가리키고 있다는 것이다. 이렇게 되면 리스트의 끝과 시작이 연결되어 있어서, 리스트를 순환형 자료구조로 사용 할 수 있다. 

 

원형 연결 리스트의 구현은 일반적인 연결 리스트와 매우 유사하지만 마지막 노드의 포인터가 Null이 아니라 첫 번째 노드를 가리키게 되는 것 차이점이다. 리스트의 마지막에 새로운 노드를 추가 하게되면, 마지막 노드 다음에 새로운 노드를 추가하고, 마지막 노드의 포인터를 첫 번째 노드를 가리키도록 수정해주면 된다.

---

자바에서의 LinkedList

선언방법

지네릭스를 사용하여 타입을 제한 할 수 있다. 

 LinkedList<String> linkedList = new LinkedList<String>();

 

요소를 추가하는 방법

add 함수를 사용하여 데이터를 추가할 수 있다. 

    // add elements to linked list
    linkedList.add("apple");
    linkedList.add("banana");
    linkedList.add("cherry");

    // add an element at specific index
    linkedList.add(1, "orange");

    // add an element at first and last position
    linkedList.addFirst("grape");
    linkedList.addLast("watermelon");

 

요소를 삭제하는 방법

remove함수를 사용하여 삭제를 할 수 있다.

    // remove the first and last elements
    linkedList.removeFirst();
    linkedList.removeLast();

    // remove an element at specific index
    linkedList.remove(2);

 

요소를 가져오는 방법

get 함수를 사용하여 해당 index에 있는 값을 가져올 수 있다.

    // get an element at specific index
    String secondElement = linkedList.get(1);

    // get the first and last element
    String firstElement = linkedList.getFirst();
    String lastElement = linkedList.getLast();

 

현재 사이즈를 알아보는 방법

size 함수를 통해 알아 볼 수 있다.

    // get the size of linked list
    int size = linkedList.size();

 

비어있는지 확인하는 방법

isEmpty를 통해 확인이 가능하다.

    // check if linked list is empty
    boolean isEmpty = linkedList.isEmpty();

 

배열로 변환하는 방법

toArray 함수를 통해 변환이 가능하다.

    // convert linked list to array
    String[] array = linkedList.toArray(new String[0]);