Linked List (연결 리스트) 란?

📋 목차

❓ 연결리스트 란?

Array(배열) & List (리스트)

특징

연결 리스트 종류

연결 리스트 구현 (자바)

---

 

❓ 연결리스트 란? 

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

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룹니다.

 

🔶 Array(배열) & List (리스트)

연결 리스트를 이해하기 앞서 배열과 리스트의 컴퓨터 공학적인 개념부터 잠깐 짚고 넘어가고자 합니다.

배열은 메모리 상에 연속적인 공간을 할당받아 데이터를 저장합니다. 배열은 원소에 접근할 때 ‘인덱스(Index)’ 라는 개념을 사용하는데 원소의 데이터 주소를 가리키는 식별자입니다. 이를 통해 특정 원소에 빠르게 접근할 수 있는 장점이 있지만, 반대로 중간에 있는 원소 삽입/삭제가 느립니다.

리스트는 각 원소가 메모리 상 연속적인 공간에 할당되지 않을 수 있습니다. 즉, 첫번째 원소의 주소를 알더라도 그 다음 원소의 주소를 단순히 계산할 수 없다는 의미입니다. 리스트의 각 원소는 다음 원소를 가리키는 ‘포인터(Pointer)’ 등을 사용하여 각 원소의 순서를 구현합니다. 이런 특징으로 배열보다 데이터의 삽입/삭제가 빠른 편입니다. 앞, 뒤의 원소의 포인터만 바꿔주면 되기 때문입니다. 하지만, 인덱스를 사용하여 특정 원소에 직접 접근이 불가능하기 때문에 원소를 검색하기 위해서는 첫번째 원소부터 선형 검색을 해야하는 단점이 있습니다.

 

🔶 특징

• 단순 연결 리스트 (Singly Linked List)
  • 각 노드가 다음 노드에 대해서만 참조하는 가장 단순한 형태의 연결 리스트 입니다.
  • Head노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 사용하지 못하는 단점이 있습니다.
  • 보통 Queue(큐)를 구현할 때 주로 사용합니다.
  • FAT 파일 시스템이 단일 연결 리스트로 파일 청크(동적 메모리로 할당되는 영역)을 연결합니다.

         

출처 : https://devowen.com/210

 

 

• 이중 연결 리스트 (Double Linked List)
  
  • 각 노드가 이전 노드, 다음 노드에 대해서 참조하는 형태의 연결 리스트 입니다.
  • 삭제가 간편하며 단일 연결 리스트에 비해 데이터 손상에 강하지만, 관리할 참조가 2개이기 때문에 삽입이나 정렬의 경우 작업량이 더 많습니다.

         

출처 : https://devowen.com/210

 

• 원형 연결 리스트 (Circular Linked List)
  • 연결 리스트에서 마지막 요소가 첫번째 요소를 참조합니다.
  • 스트림 버퍼의 구현에 많이 사용합니다.

         

출처 : https://devowen.com/210

 

🔶 연결 리스트 구현 (자바)

 

/*
 * @ 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 위치로 이동

						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();
    }
}

 

---

reference

https://devowen.com/210

DS #2. 연결 리스트 (LinkedList)

 

https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

연결 리스트 - 나무위키

 

https://freestrokes.tistory.com/84

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