연결 자료구조 - 노드, 단순 연결 리스트, 원형 연결 리스트, 이차 연결 리스트, 자바 구현

1. 노드

연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위로 저장해야 한다. 이러한 단위 구조를 노드라고 한다.

 

• 데이터 필드(Data Filed): 원소의 값을 저장, 그림에서는 Content
• 링크 필드(Link Field): 다음 노드의 주소를 저장, 그림에서는 Address
• 노드의 끝을 표시하기 위해서 마지막 노드의 링크 필드에 null을 저장

출처: BeginnersBook

 

2. 단순 연결 리스트(Singly Linked List)

단순 연결 리스트의 특징

1. 메모리 활용 유연성

순차 선형 리스트는 연속된 메모리 공간을 확보해야한다. 하지만 연결 리스트는 이전의 노드가 다음 노드의 주소를 가지고 있어서 메모리 공간 어디는 값을 저장할 수 있다.

 

2. 읽기 연산 효율성

첫번째 노드의 메모리 주소만 알기 때문에 특정 인덱스를 값을 알기 위해서는 첫 번째 인덱스부터 순차적으로 연산해야 한다. 예를 들어 인덱스 2를 찾는다면 인덱스 0부터 시작하여 인덱스 0에 있는 인덱스 1의 주소를 찾은 뒤 인덱스 1에 있는 인덱스 2의 주소를 찾아야 한다.

효율성은 O(N)이다. 효율성이 O(1)인 순차 선형 리스트와 크게 효율성이 떨어진다.

 

3. 검색 연산 효율성

첫번째 인덱스부터 일치하는 값을 찾을 때까지 순차적으로 모든 노드를 뒤져야 한다. 찾는 값이 없는 최악의 경우에 효율성은 O(N)이다. 

 

4. 삽입 연산 효율성

순차 선형 리스트와 달리 단순 연결 리스트의 삽입 연산에는 물리적 순서를 유지하기 위해 노드들을 이동시키지 않는다. 링크 필드의 참조값에 대한 연산만으로 쉽게 삽입 연산을 수행할 수 있다.

하지만 삽입하려는 위치 한단계 전 노드를 찾기 위해 첫 번째 노드부터 차례대로 검색을 해야 해서 O(N)이 걸린다.

 

5. 삭제 연산 효율성

삽입과 매우 유사하다. 노드들이 이동하지 않고 필드의 참조값에 대한 연산으로 삭제연산을 수행할 수 있다. 삭제하고자 하는 노드를 찾는다. 그다음 한 단계 전의 노드가 가리키는 주소를 삭제될 노드의 다음 노드로 변경한다. 효율성은 O(N)이다.

 

표: 순차 선형 리스트와 연결 리스트의 효율성 비교

연산	순차 선형 리스트	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))
삭제	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))

 

연결리스트를 사용하면 효율적인 예시

- 한 리스트를 검사해서 많은 원소를 삭제할 때

• 순차 선형 리스트, 연결 리스트의 검사 단계에서는 모두 N단계가 걸린다. 하지만 삭제 단계에서는 연결 리스트가 압도로적으로 효율적이다. 순차 선형 리스트에서는 값을 하나 삭제할 때마다 빈 공간을 메꾸기 위해 나머지 데이터를 왼쪽으로 이동시켜야 해서 O(N) 단계가 걸린다. 하지만 연결리스트는 삭제마다 한 단계만 걸린다.
• 1000개로 이뤄진 리스트에서 100개를 삭제할 경우
• 순차 선형 리스트는 읽기 1,000단계 + 삭제 100,000단계(삭제 데이터 100개 x N)
• 연결 리스트는 읽기 1,000단계  + 삭제 100단계가 걸린다.

 

 

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

• 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만드는 연결 리스트이다.
• 단순 연결 리스트에서 선행 노드에 접근하기 어렵다는 점을 개선하였다.
• 하지만 리스트의 링크가 한 방향으로만 되어있어서, 현재 노드 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 한다는 문제점이 있다.

출처: GeeksforGeeks

 

4. 이중 연결 리스트(Doubly Linked List)

• 양쪽 방향으로 순회할 수 있도록 연결한 리스트이다.
• 노드 구조는 두 개의 링크 필드와 한 개의 데이터 필드로 구성한다.
• 리스트를 만들때 첫 노드와 마지막 노드를 선언한다.
• 항상 첫 노드와 마지막 노드를 모두 알고 있으므로 각각 O(1)에 접근할 수 있다.
• 큐에서의 데이터 삽입과 삭제를 모두 O(1)에 할 수 있다.

출처: GeeksforGeeks

 

5. [자바] 단순 연결 리스트 구현 프로그램

package LinkedList;

public class Ex6_1_SinglyLinkedList {
    public static void main(String[] args) {
        LinkedList l = new LinkedList();
        System.out.println("1. 공백 리스트에 노드 3개 삽입하기");
        l.insertLastNode("1");
        l.insertLastNode("3");
        l.insertLastNode("6");
        l.printList();

        System.out.println("2. 3월 노드 뒤에 4월 노드 삽입하기");
        ListNode pre = l.searchNode("3");
        if(pre == null) {
            System.out.println("검색실패: 찾는 데이터가 없습니다.");
        } else {
            l.insertMiddleNode(pre, "4");
            l.printList();
        }

        System.out.println("3. 리스트의 노드를 역순으로 바꾸기");

        System.out.println("4. 리스트의 마지막 노드 삭제하기");
        l.deleteLastNode();
        l.printList();
    }
}


class LinkedList {
    private ListNode head;

    public LinkedList() {
        head = null;
    }

    public void insertMiddleNode(ListNode pre, String data) {
        ListNode newNode = new ListNode(data);
        newNode.link = pre.link;
        pre.link = newNode;
    }

    public void insertLastNode(String data) {
        ListNode newNode = new ListNode(data);

        if(head == null) {
            head = newNode;
        } else {
            ListNode temp = head;
            while(temp.link != null) {
                temp = temp.link;
            }
            temp.link = newNode;
        }
    }

    public void deleteLastNode() {
        ListNode pre, temp;

        if(head == null) {
            System.out.println("삭제실패: 값이 없습니다.");
            return;
        } else {
            pre = head;
            temp = head.link;
            while (temp.link != null) {
                pre = temp;
                temp = temp.link;
            }
            pre.link = null;
        }
    }

    public ListNode searchNode(String data) {
        ListNode temp = this.head;
        while (temp != null) {
            if(data == temp.getData()) {
                return temp;
            } else {
                temp = temp.link;
            }
        }
        System.out.println("검색실패: " + data + "은(는) 없습니다.");
        return temp;
    }

    public void reverseList() {

    }

    public void printList() {
        ListNode temp = this.head;
        System.out.printf("l = ( ");
        while (temp != null) {
            System.out.printf(temp.getData());
            temp = temp.link;

            if(temp != null) {
                System.out.printf(", ");
            }
        }
        System.out.println(" )");
    }

}


class ListNode {
    private String data;
    public ListNode link;

    public ListNode(String data) {
        this.data = data;
        link = null;
    }

    public ListNode(String data, ListNode link) {
        this.data = data;
        this.link = link;
    }

    public String getData() {
        return data;
    }
}

 

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음