[자료구조 Java] 단일 연결리스트(Singly Linked List) 개념 정리 + 자바로 구현하기

 

연결리스트란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 데이터 구조

노드는 데이터 구조를 구성하는 하나의 객체를 의미한다.

포인터는 주소값을 저장하는 것으로 이 포인터가 다른 노드의 주소값을 저장하는 방식으로 노드들이 연결되어 있다.

 

 

연결리스트 종류: 단일 연결리스트, 이중 연결리스트, 원형 연결리스트

 

 

단일 연결리스트란?

각 노드가 앞에서 뒤로의 연결만을 가진 연결리스트

단일 연결이기에 각 노드의 포인터에는 후행 노드의 주소값이 저장되어 있다.

따라서 앞에서 뒤로의 접근은 가능하지만 뒤에서 앞으로의 접근은 불가하다.

 

 

단일 연결 리스트의 구성

하나의 노드는 데이터와 포인터로 이루어져 있다.

단일 연결이기에 포인터는 다음 노드의 주소값만 저장하고 있으며 다시 앞으로 돌아가는 등의 연산은 불가능하다.

head는 가장 첫 노드의 주소값을 저장하고 있는 별도의 변수로 단일 연결 리스트에 접근하기 위해 가장 처음 접근하는 변수이다.

 

public class Node<T> {
    Node<T> next = null;
    T data = null;
}

 

public class SinglyLinkedList<T> {
    Node<T> head = null;
    int length = 0;

실제 구현은 제너릭을 사용하여 필요에 맞는 자료형을 쓸 수 있게 구현하였다.

 

 

단일 연결 리스트 삽입

삽입하려는 위치의 선행 노드(NodeB)의 포인터에 저장된 주소값(후행 노드의 주소값 0x10)을 임시 저장한다.

그리고 선행 노드의 포인터에 삽입하려는 노드의 주소값(0x18)을 저장한다.

새로운 노드에는 임시 저장한 주소값(0x10)을 저장한다.

 

삽입하려는 위치의 후행 노드 주소를 임시저장하는 것이 중요한데 이를 하지 않고 선행 노드에 저장된 다음 노드 주소값을 바꾸면 단일 연결 형태이기에 해당 노드 이후의 노드에 영원히 접근할 수 없기 때문이다.

 

삽입하려는 위치가 맨 앞이라면 head가 가리키는 주소값을 앞 노드의 포인터에 저장된 주소값에 대응된다고 보고 대신 조정한다. 이후는 중간에 노드를 삽입하는 것과 동일한다.

 

    public void add(int index, T data) {
        Node<T> newNode = new Node<>();
        newNode.data = data;

        if (index == 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            Node<T> preNode = findNode(index - 1);
            newNode.next = preNode.next;
            preNode.next = newNode;
        }
        this.length++;
    }
    
   public void addLast(T data) {
        add(length, data);
    }

    public void addFirst(T data) {
        add(0, data);
    }

 

 

단일 연결 리스트 삭제

 

삭제하려는 노드의 앞 노드(NodeB) 포인터 값을 삭제하려는 노드의 포인터 값(0x18)로 바군다.

Java의 경우 Garbage Collector에 의해 노드가 참조되지 않으면 자동으로 메모리를 해제하기에 별도의 조치가 필요하지 않다.

반면 C언어의 경우 동적으로 할당한 메모리를 free()함수 등을 통해 해제해야 한다.

 

삭제하려는 노드가 맨 앞노드(NodeA)인 경우 동일한 논리로 Head의 참조값을 맨 앞노드가 참조하던 주소값으로 바꾸면 된다. 

 

    public void deleteByIndex(int index) {
        if (index == 0) {
            this.head = this.head.next;
        } else {
            Node<T> preNode = findNode(index - 1);
            preNode.next = preNode.next.next;
        }
        this.length--;
    }

    public void delete(T deleteData) {
        int deleteIndex = getIndex(deleteData);
        deleteByIndex(deleteIndex);
    }

    public void deleteAll() {
        this.head.next = null;
        length = 0;
    }

 

 

단일 연결 리스트의 장점과 단점

 

장점

 

1. 공간을 미리 할당하지 않는다.

 

배열의 경우 미리 메모리 공간을 할당하기에 공간적으로 비효율적이다. 단일 연결 리스트의 경우 삽입, 삭제에 따른 메모리 할당을 런타임 환경에서 하기에 상대적으로 메모리를 절약한다.

 

2. 삽입/삭제가 빠르다

 

배열은 중간 인덱스의 데이터가 삭제된 경우 삭제되는 데이터 이외에도 다른 데이터를 재배치하는 것이 필요하다. 하지만 단일 연결 리스트는 단순히 삭제되는 노드의 앞 노드의 포인터의 주소값만 변경해주면 된다. 따라서 빈번한 삽입, 삭제에 배열보다 훨씬 유리하다.

 

단점

 

1. 접근 연산에 불리하다.

 

원하는 데이터의 인덱스를 아는 경우 배열은 시간복잡도 O(1). 반면 단일 연결 리스트는 인덱스가 별도로 존재하지 않고 몇 번재 데이터인지를 알고 있어도 항상 head에서 시작해서 첫 번째 노드부터 접근해야 하기 때문에 접근 속도가 훨씬 느리다.

 

 

시간복잡도

 

접근은 인덱스를 아는 경우, 검색은 인덱스를 모르는 경우에 해당.

 

결론

실제 프로그래밍시 단일 연결 리스트를 사용하는 경우는 거의 없다. 노드에 하나의 주소를 저장하는 변수가 추가된다는 점을 제외하고는 이중 연결리스트가 모든 면에서 단일 연결리스트 보다 우위에 있기 때문이다. 실제로 자바 collections에 있는 LinkedList만 해도 단일 연결리스트가 아닌 이중 연결리스트로 구현되어 있다. 하지만 이중 연결리스트는 단일 연결리스트에서 선행노드 -> 후행노드, 선행노드 <- 후행노드로의 양방향 접근을 추가한 것이기에 이중 연결리스트를 이해하는데 큰 도움이 된다.

 

 

 

실행 코드

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList<String> list = new SinglyLinkedList<>();

        list.addFirst("A");
        list.add(1, "B");
        list.add(2, "C");
        list.add(3, "D");
        list.addLast("E");
        list.display();
        System.out.println("A의 index: " + list.getIndex("A"));
        System.out.println("E의 index: " + list.getIndex("E"));
        System.out.printf("A가 있는지?: " + list.isInList("A") + "\n");
        System.out.printf("F가 있는지?: " + list.isInList("F") + "\n\n");

        list.replace(0, "1");
        list.replace(2, "3");
        list.replace(4, "5");
        list.display();

        System.out.print("값이 5인 index4 노드 삭제 \n");
        list.deleteByIndex(4);
        System.out.printf("5가 있는지: " + list.isInList("5") + "\n");
        System.out.printf("isEmpty?: " + list.isEmpty() + "\n");
        System.out.println("deleteAll()함수로 전체 삭제");
        list.deleteAll();
        System.out.printf("isEmpty?: " + list.isEmpty() + "\n");
    }
}

 

- 실행 결과 -

 

 

전체 구현 코드

https://github.com/you88311/data-structure/tree/main/singly-linked-list/src

GitHub - you88311/data-structure

 

 

---

참고

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼

 

C언어로 쉽게 풀어쓴 자료구조 - 청인국, 공용해, 하상호 지음