[JAVA] 자료구조 - 연결 리스트(Linked List)

---

01. 연결 리스트(Linked List)

• 데이터를 링크로 연결하여 관리하는 자료구조
• 자료의 순서 존재, But 메모리 상 연속성 X (배열과 다름)

<연결 리스트 구성>

---

02. 장점과 단점

   - 장점

• 데이터 공간을 미리 할당할 필요 X
• 리스트의 길이가 가변적 → 데이터 삭제/추가 용이

   - 단점

• 연결 구조를 위한 별도의 데이터 공간 필요
• 연결 정보를 찾는 시간 필요(접근속도가 상대적 느림)
• 데이터 추가/삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업 필요

---

03. 연결 리스트의 기본 구조

   (1) 노드 (Node): 데이터 저장 단위, 값/포인터로 구성 (*포인터(Pointer): 다음 노드나 이전 노드의 연결 정보)

---

   (2) 데이터 추가: 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요

      - 가장 앞(head)에 데이터 추가

         1️⃣ 추가 할 데이터 담을 노드 생성

         2️⃣ 링크 연결 작업

         3️⃣ head 이전 작업 (새로 추가한 노드: head)

      - 중간에 데이터 추가

         1️⃣ 추가할 데이터 담을 노드 생성

         2️⃣ head 부터 데이터 추가 위치 직전까지 순회

         3️⃣ 링크 연결 작업 (새로 추가한 노드의 이전: 직전 노드 , 새로 추가한 노드의 이후: 기존에 존재하던 노드)

      - 가장 끝(tail)에 데이터 추가

         1️⃣ 추가할 데이터를 담을 노드 생성

         2️⃣ head 부터 tail까지 순회 

         3️⃣ 링크 연결 작업 (새로 추가한 노드: tail)

---

   (3) 데이터 삭제: 데이터 삭제 위치(head, 중간, tail)에 따른 연결 작업 필요

      - 가장 앞(head)에 데이터 삭제

         1️⃣ 삭제 대상 노드 지정

         2️⃣ head 이전 작업

         3️⃣ target 삭제

      - 중간에 데이터 삭제

         1️⃣ head부터 삭제 target까지 순회, 해당 노드 지정

         2️⃣ 삭제 대상 이전 / 이후 링크 연결 작업

         3️⃣ target 삭제

      - 가장 끝(tail)에 데이터 삭제

         1️⃣ head부터 끝까지 순회

         2️⃣ 끝 노드 삭제

         3️⃣ 삭제 이전 노드의 링크 처(끊어줌)

 

* JAVA에는 값을 null로 바꾸는 과정을 통해 자동으로 메모리를 관리하므로 코드 작성 시 head 이전만 구현하면 됨 *

---

04. 구현하기 - 구조 익히기

   (1) 단순 연결 리스트

// 노드
class Node {
    int data;
    Node next;  //다음 노드 가리킴

    Node(){}
    Node(int data, Node next){
        this.data = data;
        this.next = next;
    }
}

class LinkedList {
    Node head;

    LinkedList(){}
    LinkedList(Node node){
        this.head = node;
    }

    //  연결 리스트 비어있는지 확인
    public boolean isEmpty(){
        return this.head == null;
    }

    //  연결 리스트의 맨 뒤에 데이터 추가
    public void addData(int data){
        if(this.head == null){  // 가장 처음에 노드가 없다면
            this.head = new Node(data, null);
        } else {  // 노드들이 존재하면
            Node cur = this.head;  // 처음부터
            while(cur.next != null){  // 끝까지 순회함
                cur = cur.next;
            }
            cur.next = new Node(data, null);  // 마지막에 노드를 추가함
        }
    }

    //  연결 리스트의 맨 뒤의 데이터 삭제
    public void removeData(){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        Node cur = this.head;
        Node prev = cur;

        while(cur.next != null){
            prev = cur;
            cur = cur.next;
        }

        if(cur == this.head){  // 헤드인 경우
            this.head = null;
        }else{  // 마지막을 찾은 경우
            prev.next = null;
        }
    }

    //  연결 리스트에서 데이터 찾기
    public void findData(int data){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        Node cur = this.head;
        while (cur.next != null){  // 처음부터 순회하며
            if(cur.data == data){  // 데이터가 존재하면
                System.out.println("Data Exits");  // 찾았다는 문구 출력
                return;
            }
            cur = cur.next;  //다음으로 넘어감
        }
        System.out.println("Data not found");  // 못 찾은 경우 문구 출력
    }

    //  연결 리스트의 모든 데이터 출력
    public void showData(){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        Node cur = this.head;
        while(cur != null){
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }

}

   (2) (1)의 단순 연결 리스트 구현 완성

class LinkedList2 extends LinkedList{
    LinkedList2(Node node){
        this.head = node;
    }

    //연결리스트에 데이터 추가
    // beforeData가 null인 경우, 가장 뒤에 추가
    // beforeData에 값이 있는 경우. 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData){
        if(this.head == null){
            this.head = new Node(data, null);
        }else if(beforeData == null){
            Node cur = this.head;
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = new Node(data, null);
        }else{
            Node cur = this.head;
            Node prev = cur;  // cur을 쫓아다니는 prev
            while(cur != null){  // cur을 이동시킴
                if(cur.data == beforeData){  // 같은 경우 앞에 추가
                    if(cur == this.head){  // 헤드에 같은 데이터가 존재하면
                        this.head = new Node(data, this.head);  //헤드는 새로운 데이터, 새로운 헤드는 이전 헤드를 넥스트로 가짐
                    }else{  // 헤드가 아닌 경우에 데이터가 존재하면
                        // prev는 cur의 앞이므로 prev의 넥스트에 값이 추가됨,
                        // 넥스트에 노드는 다음 노드로 현재 노드를 가리킴
                        prev.next = new Node(data, cur);
                    }
                    break;
                }
                cur = cur.next;
            }
        }
    }

    // 데이터 지우기
    public void removeData(int data){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        Node cur = this.head;
        Node pre = cur;

        while(cur != null){
            if(cur.data == data){  // 데이터를 찾으면
                if(cur == this.head){  // 만약 데이터가 헤드라면
                    this.head = cur.next;  //헤드는 다음 노드가 되고
                }else{  // 아닌 경우
                    pre.next = cur.next;  // 이전의 노드의 다음은 현재의 노드의 다음을 가리키면서 가운데에 있는 노드를 삭제함
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }
}

 

   (3) 양방향 연결 리스트

class NodeBi {
    int data;
    NodeBi next;
    NodeBi prev;

    public NodeBi(int data, NodeBi next, NodeBi prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList{
    NodeBi head;
    NodeBi tail;

    DoublyLinkedList(NodeBi node){
        this.head = node;
        this.tail = node;
    }

    public boolean isEmpty(){
        return this.head==null;
    }

    public void addData(int data, Integer beforeData){
        if(this.head == null){
            this.head = new NodeBi(data, null, null);
            this.tail = this.head;  // 가장끝을 관리하고 있음
        }else if(beforeData == null){
            this.tail.next = new NodeBi(data, null, this.tail);  //새로운 노드도 이전의 꼬리를 이전으로 가짐
        }else{
            NodeBi cur = this.head;
            NodeBi pre = cur;
            while(cur != null){
                if(cur.data == beforeData){  //데이터가 있음
                    if(cur == this.head){  //헤드에 있다면
                        //헤드는 새로운 노드를 가리킴, 새로운 노드는 넥스트로: 이전 헤드, 이전으로: null을 가짐
                        this.head = new NodeBi(data, this.head, null);
                        this.head.next.prev = this.head;  //헤드의 다음의 이전은 원래 null -> 새로 만들어진 헤드를 가리킴
                    }else{  //헤드가 아닌 경우
                        pre.next = new NodeBi(data, cur, pre);  //이전의 넥스트, 즉 현재 자리에 새로운 노드 추가
                        cur.prev = pre.next;  //현재의 이전은 이전의 넥스트
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            }
        }
    }

    public void removeData(int data){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        NodeBi cur = this.head;
        NodeBi pre = cur;

        while(cur != null){
            if(cur.data == data){// 찾는 데이터가
                if(cur == this.head && cur == this.tail){  // 헤드임과 동시에 마지막일때
                    this.head = null;
                    this.tail = null;
                }else if(cur == this.head){  //헤드일때
                    this.head = cur.next;  //헤드를 현재의 넥스트로 지정
                    this.head.prev = null;  //새로 바뀐 헤드의 이전은 없앰
                }else if(cur == this.tail){  //꼬리일때
                    this.tail = this.tail.prev;  //꼬리의 이전을 꼬리로 지정
                    this.tail.next = null;  //새로 바뀐 꼬리의 넥스트는 없앰
                }else{  //중간에 있을 때
                    pre.next = cur.next;  //이전의 다음은 현재의 다음
                    cur.next.prev = pre;  //현재의 다음의 이전은 이전꺼
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public void showData(){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        NodeBi cur = this.head;
        while(cur != null){
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void showDataFromTail(){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        NodeBi cur = this.tail;
        while(cur != null){
            System.out.print(cur.data+" ");
            cur = cur.prev;
        }
        System.out.println();
    }
}

 

   (4) 원형 연결 리스트

class CircularLinkedList {
    NodeBi head;
    NodeBi tail;

    public CircularLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
        node.prev = this.head;
    }

    public boolean isEmpty(){
        return this.head == null;
    }
    // 연결 리스트에 데이터 추가
    // before_data 가 null 인 경우, 가장 뒤에 추가
    // before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData){
        if(this.head == null){  //만약 헤드가 없을 때
            NodeBi newNodeBi = new NodeBi(data, null,null);  //헤드에 새로운 데이터 생성
            this.head = newNodeBi;  //헤드는 새로운 노드
            this.tail = newNodeBi;  //꼬리도 새로운 노드
            newNodeBi.next = newNodeBi;  //새로운 노드의 넥스트: 새로운 노드 -> 나자신
            newNodeBi.prev = newNodeBi;  //새로운 노드의 이전: 새로운 노드 -> 나자신
        }else if(beforeData == null){  //이전 데이터가 널로 들어오는 경우 -> 맨 마지막에 넣어줌
            NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);  //새로운 노드는 꼬리에 연결
            this.tail.next = newNodeBi;  //꼬리의 넥스트: 새로운 노드
            this.head.prev = newNodeBi;  //헤드의 이전: 새로운 노드
            this.tail = newNodeBi;  //현재 꼬리: 새로운 노드
        } else{  //beforeData가 있는 경우
            NodeBi cur = this.head;
            NodeBi pre = cur;
            do {
                if(cur.data == beforeData){  //데이터를 찾으면
                    if(cur == this.head){  //헤드일때
                        NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);  //새로운 노드 생성, 이전: 꼬리, 넥스트: 원래 헤드
                        this.tail.next = newNodeBi;  //꼬리의 다음: 새로운 노드
                        this.head.prev = newNodeBi;  //헤드의 이전: 새로운 노드
                        this.head = newNodeBi;  //새 해드: 새로운 노드
                    }else{  //헤드가 아닌 경우
                        NodeBi newNodeBi = new NodeBi(data, cur, pre);  //새로운 노드 생성, 다음: 현재, 이전: 이전
                        pre.next = newNodeBi;  //이전의 다음: 새로운 노드
                        cur.prev = newNodeBi;  //현재의 이전: 새로운 노드
                    }
                    break;
                }
                pre = cur;
                cur = cur.next;
            }while (cur != this.head);
        }
    }

    //  연결 리스트에서 특정 값을 가진 노드 삭제
    public void removeData(int data){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        NodeBi cur = this.head;
        NodeBi pre = cur;
        while (cur != null){
            if(cur.data == data){
                if(cur == this.head && cur == this.tail){  //데이터가 꼬리이자 헤드일때
                    this.head = null;
                    this.tail = null;
                }else if(cur == this.head){  //데이터가 헤드인 경우
                    cur.next.prev = this.head.prev;  //현재의 다음의 이전(즉, 지금 나의 자리)은 헤드의 이전 노드 == tail
                    this.head = cur.next;  //현재 헤드는 현재의 다음 노드
                    this.tail.next = this.head;  //꼬리의 다음은 새로 바뀐 현재 노드
                }else if(cur == this.tail){  //데이터가 꼬리인 경우
                    pre.next = this.tail.next;  // == this.tail.next
                    this.tail = pre;  //꼬리는 꼬리의 이전으로 바뀜
                    this.head.prev = this.tail;  //헤드의 이전, 즉 꼬리 다시 입력
                }else{  //데이터가 중간에 있는 경우
                    pre.next = cur.next;
                    cur.next.prev = pre;
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public void showData(){
        if(this.isEmpty()){
            System.out.println("List is Empty");
            return;
        }

        NodeBi cur = this.head;
        while (cur.next != this.head){  //원형이므로
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println(cur.data);  //가장 끝노드는 출력이 안되므로
    }
}

---