연결 리스트 (Linked List)

출처 : https://medium.com/@ramyjzh/data-structures-for-dummies-linked-lists-7116a528a097

 

 

데이터를 노드(Node)로 구성하고 노드들이 포인터를 통해 연결된 리스트

데이터의 동적인 관리와 삽입/삭제 연산이 주로 필요한 경우에 유용하며, 특히 크기가 미리 예측하기 어려운 상황에서 활용됨

• 장점
  크기의 제한이 없음: 연결 리스트는 동적으로 크기를 조절할 수 있으므로, 데이터의 추가 및 삭제가 자유로움
  삽입과 삭제가 용이: 원하는 위치에 노드를 추가하거나 삭제하기가 상대적으로 간단하며 포인터로 연결되어 있어 가리키는 노드만 변경
  메모리 효율적 활용: 크기가 동적이므로 필요한 메모리만 사용하며, 메모리의 재사용이 가능
  데이터의 순차적 배치: 데이터 입력시 주소가 순차적이지 않아 요소를 메모리의 어느곳에나 배치할 수 있어 메모리 관리 측면에서 유용
• 단점
  랜덤 액세스 불가: 연결 리스트는 노드들이 포인터로 연결되어 있어 특정 위치의 데이터에 랜덤으로 접근하는 것이 어려여 순차 접근이 일반적임
  추가적인 메모리 소요: 각 노드마다 추가적인 포인터 공간이 필요하므로, 배열에 비해 메모리 사용량이 더 많을 수 있음
  검색 속도 저하: 특정 데이터를 검색할 때 모든 노드를 순차적으로 탐색해야 하므로, 검색 속도가 배열에 비해 느림

출처 : https://dev.to/ivywalobwa/singly-linked-list-f2m

단순 연결리스트(Sinlgy Linked List)

데이터를 노드(Node)로 구성하고, 각 노드는 다음 노드를 가리키는 링크(포인터)를 가지는 자료구조

출처 : https://www.geeksforgeeks.org/types-of-linked-list/

package datastructure.linear;

// 노드 클래스 정의
class SinglyNode {
    int data;
    SinglyNode next;

    public SinglyNode(int data) {
        this.data = data;
        this.next = null;
    }
}

// 단순 연결리스트 클래스 정의
class SinglyLinkedList {
    private SinglyNode head;

    public SinglyLinkedList() {
        this.head = null;
    }

    // 노드 추가 메서드
    public void addNode(int data) {
        SinglyNode newNode = new SinglyNode(data);
        if (head == null) {
            head = newNode;
        } else {
            SinglyNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 노드 출력 메서드
    public void display() {
        SinglyNode current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

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

        list.addNode(1);
        list.addNode(2);
        list.addNode(3);

        list.display(); // 출력: 1 -> 2 -> 3 -> null
    }
}

 

이중 연결 리스트(Doublely LinkedList)

각 노드가 이전 노드와 다음 노드를 가리키는 형태의 연결 리스트

출처 : https://www.geeksforgeeks.org/types-of-linked-list/

package datastructure.linear;

// 노드 클래스 정의
class DoublyNode {
    int data;
    DoublyNode prev;
    DoublyNode next;

    public DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// 이중 연결리스트 클래스 정의
class DoublyLinkedList {
    private DoublyNode head;
    private DoublyNode tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 노드 추가 메서드
    public void addNode(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 노드 출력 메서드 (순방향)
    public void displayForward() {
        DoublyNode current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 노드 출력 메서드 (역방향)
    public void displayBackward() {
        DoublyNode current = tail;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.prev;
        }
        System.out.println("null");
    }
}

public class DoublyLinkedListTest {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();

        list.addNode(1);
        list.addNode(2);
        list.addNode(3);

        System.out.println("Forward Display:");
        list.displayForward(); // 출력: 1 -> 2 -> 3 -> null

        System.out.println("Backward Display:");
        list.displayBackward(); // 출력: 3 -> 2 -> 1 -> null
    }
}

 

원형 연결 리스트(Circular LinkedList)

노드들이 원형으로 연결된 자료구조로서 마지막 노드가 첫 번째 노드를 가리키며, 리스트의 끝을 검사하는 데 유용

출처 : https://www.geeksforgeeks.org/types-of-linked-list/

 

package datastructure.linear;

// 노드 클래스 정의
class CircularNode {
    int data;
    CircularNode next;

    public CircularNode(int data) {
        this.data = data;
        this.next = null;
    }
}

// 원형 연결리스트 클래스 정의
class CircularLinkedList {
    private CircularNode head;
    private CircularNode tail;

    public CircularLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 노드 추가 메서드
    public void addNode(int data) {
        CircularNode newNode = new CircularNode(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head; // 첫 번째 노드를 가리키도록 설정
        } else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head; // 마지막 노드가 첫 번째 노드를 가리키도록 설정
        }
    }

    // 원형 연결리스트 출력 메서드
    public void display() {
        if (head == null) {
            System.out.println("리스트가 비어 있습니다.");
            return;
        }

        CircularNode current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println();
    }
}

public class CircularLinkedListTest {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        list.addNode(1);
        list.addNode(2);
        list.addNode(3);

        System.out.println("원형 연결리스트 출력:");
        list.display();
    }
}