Java로 연결 리스트(Linked List) 구현하기

Java로 연결 리스트(Linked List) 구현하기

Java로 연결 리스트(Linked List)를 구현하는 방법에 대해 알아보겠습니다.

1. 연결 리스트(Linked List)

연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당합니다.

배열에 비해서 데이터의 추가/삭제가 용이하나,  인덱스가 없는 리스트의 특징으로 인하여 특정 요소에 접근하기 위해서는 순차 탐색을 필요로 하므로 일반적으로 탐색 속도가 떨어집니다. 즉, 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것을 권장합니다. (자바 LinkedList의 경우 인덱스를 사용하여 연산을 수행할 수 있도록 get(index) 형태의 메서드를 제공하지만, 메서드 내부의 동작은 순차 탐색으로 이루어져 있습니다)

다음은 연결 리스트의 종류입니다.

• 단일 연결 리스트(Singly Linked List)
  각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트입니다.
  일반적으로 큐를 구현할 때 사용됩니다.
  Head 노드를 잃어버려 참조하지 못하는 경우 데이터 전체를 사용 못하게 되는 단점이 있습니다.
  FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)를 연결합니다.
• 이중 연결 리스트(Doubly Linked List)
  각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트입니다.
  삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하지만, 관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많아집니다.
• 원형 연결 리스트(Circular Linked List)
  연결 리스트에서 마지막 요소가 첫번째 요소를 참조합니다.
  스트림 버퍼의 구현에 많이 사용됩니다.

1.1. 연결 리스트의 구현

다음은 Java로 구현한 연결 리스트의 소스코드입니다.

/*
 * @ TITLE Linked List (연결 리스트)
 */
// List를 구성하는 Node 클래스
class ListNode{
    private String data;    // 데이터 저장 변수
    public ListNode link;    // 다른 노드를 참조할 링크 노드
    
    public ListNode() {
        this.data = null;
        this.link = null;
    }
    
    public ListNode(String data) {
        this.data = data;
        this.link = null;
    }
    
    public ListNode(String data, ListNode link) {
        this.data = data;
        this.link = link;
    }
    
    public String getData() {
        return this.data;
    }
}
public class LinkedList {
    
    private ListNode head;    // ListNode 타입의 head 노드 인스턴스 변수
    
    // LinkedList 생성자
    public LinkedList() {
        head = null;    // head 노드 초기화
    }
    
    // Node 삽입 (중간에 삽입)
    public void insertNode(ListNode preNode, String data) {       
        ListNode newNode = new ListNode(data);    // 새로운 노드 생성
        
        // preNode.link는 preNode의 다음 노드이므로,
        // newNode.link = preNode.link는 새로운 노드의 link가 preNode의 다음 노드를 참조하도록 함. 
        newNode.link = preNode.link;
        
        // preNode의 link가 새로운 노드를 참조하도록 함.
        // 최종적으로 'preNode -> newNode -> 기존 preNode의 다음 노드 '이렇게 구성됨.
        preNode.link = newNode;
    }
    
    // Node 삽입 (마지막에 삽입)
    public void insertNode(String data) {
        ListNode newNode = new ListNode(data);    // 새로운 노드 생성
        if(head == null) {
            // head 노드가 null인 경우 새로운 노드를 참조하도록 함
            this.head = newNode;
        } else {
            // head 노드가 null이 아닌 경우 temp 노드가 head를 참조.
            // tempNode는 마지막 노드를 찾아서 참조하기 위해 사용.
            ListNode tempNode = head;
            
            // temp 노드의 link가 null이 아닐 때까지 다음 노드를 참조.
            // tempNode.link는 다음 노드를 참조하고 있으므로,
            // tempNode = tempNode.link는 tempNode에 다음 노드를 참조하도록 하는 것.
            // while문이 모두 실행되면 tempNode는 가장 마지막 노드를 참조하게 됨.
            while(tempNode.link != null) {
                tempNode = tempNode.link;    // 다음 노드를 참조
            }
            
            // tempNode(마지막 노드)의 link가 다음 노드를 참조하도록 함. 
            tempNode.link = newNode;
        }
    }
    
    // Node 삭제(중간 노드 삭제)
    public void deleteNode(String data) {
        // preNode는 head가 가리키는 노드를 할당
        ListNode preNode = head;
        // tempNode는 head가 가리키는 노드의 다음 노드. 즉, preNode의 다음 노드를 할당
        ListNode tempNode = head.link; 
        
        // 주어진 데이터가 preNode의 데이터와 일치하는 경우
        // 즉, 첫번째 노드의 데이터와 일치하는 경우
        if(data.equals( preNode.getData() )) {
            // head는 preNode의 다음 노드를 참조하도록 함.
            head = preNode.link;
            // preNode의 link는 null을 할당하여 연결을 끊음.
            preNode.link = null;
        } else {
            // tempNode가 null일 때까지 반복하여 탐색
            while(tempNode != null) {
                // 주어진 데이터와 temp 노드의 데이터가 일치할 경우.
                if(data.equals( tempNode.getData() )) {
                    // tempNode가 마지막 노드인 경우
                    if(tempNode.link == null) {
                        preNode.link = null;
                    } else {
                        // tempNode가 마지막 노드가 아닌 경우
                        // preNode의 link는 tempNode의 다음 노드를 참조.
                        // tempNode의 link는 null을 할당하여 다음 노드로의 연결을 끊음.
                        preNode.link = tempNode.link;
                        tempNode.link = null;
                    }
                    break;
                } else {
                    // 데이터가 일치하지 않을 경우 
                    // preNode에 tempNode를 할당하고, tempNode에 다음 노드 할당.
                    preNode = tempNode;
                    tempNode = tempNode.link;
                }
            }
        }
    }
    
    // Node 삭제(마지막 노드 삭제)
    public void deleteNode() {
        ListNode preNode;
        ListNode tempNode;
        
        // head 노드가 null인 경우 모든 노드가 삭제되었으므로 return
        if(head == null) {
            return;
        }
        
        // head 노드의 link가 null인 경우
        // 노드가 1개 남았을 경우
        if(head.link == null) {
            // head에 null을 할당하여 남은 노드와의 연결을 끊음.
            head = null;
        } else {
            // preNode는 head가 가리키는 노드를 할당
            preNode = head;
            // tempNode는 head가 가리키는 노드의 다음 노드. 즉, preNode의 다음 노드를 할당
            tempNode = head.link;     
            
            // tempNode의 link가 null이 아닐 때까지 한 노드씩 다음 노드로 이동.
            // preNode는 tempNode를 할당하고
            // tempNode는 tempNode의 다음 노드를 할당.
            // 이렇게 하면 preNode는 마지막 노드의 이전 노드가 되고, tempNode는 마지막 노드가 됨.
            while(tempNode.link != null) {
                preNode = tempNode;
                tempNode = tempNode.link;
            }
            
            // preNode의 link를 null로 만들어서 가장 마지막 노드를 삭제
            // 즉, preNode의 다음 노드인 tempNode로의 연결을 끊음.
            preNode.link = null;
        }
    }
    
    // Node 탐색
    public ListNode searchNode(String data) {
        ListNode tempNode = this.head;    // temp 노드에 head가 가리키는 첫 번째 할당.
        
        // temp 노드가 null이 아닐 때까지 반복하여 탐색
        while(tempNode != null) {
            // 주어진 데이터와 temp 노드의 데이터가 일치할 경우 해당 temp 노드를 return
            if(data.equals(tempNode.getData())) {
                return tempNode;
            } else {
                // 데이터가 일치하지 않을 경우 temp 노드에 다음 노드 할당.
                tempNode = tempNode.link;
            }
        }
        
        return tempNode;
    }
    
    // 리스트의 노드를 역순으로 구성
    public void reverseList() {
        ListNode nextNode = head;    // head가 참조하는 첫번째 노드를 할당.
        ListNode currentNode = null;
        ListNode preNode = null;
        
        // nextNode가 순차적으로 이동하며 currentNode의 link가 preNode를 참조하도록 함.
        // 1) preNode를 currentNode 위치로 이동
        // 2) currentNode는 nextNode 위치로 이동
        // 3) nextNode는 다음 노드 위치로 이동
        // 4) currentNode의 link는 preNode를 참조하도록 함
        while(nextNode != null) {
            preNode = currentNode;    // preNode는 currentNode 위치로 이동
            currentNode = nextNode;    // currentNode는 nextNode 위치로 이동
            nextNode = nextNode.link;    // nextNode는 다음 노드 위치로 이동
            currentNode.link = preNode;    // currentNode의 link에 preNode를 할당하여 역순으로 설정
        }
        
        head = currentNode;    // currentNode가 마지막 노드를 가리킬 때, head는 currentNode를 참조하도록 함.
    }
    
    // 연결 리스트에 저장된 모든 데이터를 출력
    public void printList() {
        ListNode tempNode = this.head;    // tempNode에 head가 가리키는 첫번째 노드를 할당
        
        // tempNode가 null이 아닐 때까지 반복하여 출력
        while(tempNode != null) {
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.link;    // temp 노드에 다음 노드(tempNode.link) 할당.
        }
        System.out.println();
    }
 
    public static void main(String args[]) {
        LinkedList linkedList = new LinkedList();    // 연결 리스트 생성
        String str = "wed";
        
        linkedList.insertNode("sun");
        linkedList.insertNode("mon");
        linkedList.insertNode("tue");
        linkedList.insertNode("wed");
        linkedList.insertNode("thu");
        linkedList.insertNode("fri");
        linkedList.insertNode("sat");
        linkedList.printList();
        
        System.out.println(linkedList.searchNode(str).getData());
        
        linkedList.deleteNode(linkedList.searchNode(str).getData());
        linkedList.printList();
        
        str = "sun";
        
        linkedList.deleteNode(linkedList.searchNode(str).getData());
        linkedList.printList();
        
        linkedList.reverseList();
        linkedList.printList();
    }
    
}

위의 코드를 실행하면 다음과 같은 결과가 출력됩니다.

이상으로 Java로 연결리스트를 구현하는 방법에 대해서 알아봤습니다.

※ 참고 문헌

• ko.wikipedia.org, 연결 리스트, https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

• donghoson.tistory.com, 링크드 리스트 구현하기, https://donghoson.tistory.com/m/157?category=799812

• namu.wiki, 연결 리스트, https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

• luckyyowu.tistory.com, 간단한 단방향 연결 리스트(Linked List) 예제 및 설명 (C 언어), https://luckyyowu.tistory.com/324