[자료구조] 연결리스트

728x90

연결리스트 (LinkedList)란?

https://miro.medium.com/max/1748/1*JG-58S8EMxVXrk7cKAaK8w.png

- 데이터를 링크로 연결해서 관리하는 자료구조

- 기본 구조 : 노드 ( 값 + 포인터 )

- 자료의 순서는 정해져 있지만, 메모리 상 연속성이 보장되지는 않음

<장점>

1. 데이터 공간을 미리 할당할 필요 없다.

2. 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이하다.

<단점>

1. 연결 구조를 위한 별도의 데이터 공간이 필요 -> 상대적 느림

2. 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요!

[ 데이터 추가 ]

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

↓

링크 연결 작업

↓

head 이전 작업 (제일 앞으로)

[ 데이터 삭제 ]

삭제 대상 노드 지정

↓

head 이전 작업

↓

delete_node 삭제 ( 링크도 함께 삭제해주기 )

유형1. 단순 연결 리스트

- 연결 리스트에 데이터 추가

- before_data가 null인 경우, 가장 뒤에 추가

- before_data가 값이 있는 경우, 해당 값을 가진 노드 앞에 추가

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 = head;}

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

    // 연결리스트 맨 뒤에 데이터 추가
    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 != null) {
            if (cur.data == data) {
                System.out.println("Data Exist !");
                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. 양방향 연결 리스트

https://velog.io/@underlier12/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%99%EC%8A%B5-03-kek5cinu4d

- 단방향 연결리스트와 달리, (prev + next) 총 2개의 노드를 갖는다.

- 데이터 추가 / 삭제 시, head인지만 확인하면 안되고, head / tail 여부를 함께 확인해야한다.

- 특히, 데이터를 삭제할 때 Node도 함께 null 값으로 바꿔주어야한다.

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

    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() {
        if (this.head == null) {
            return true;
        }
        return false;
    }

    // 연결 리스트에 데이터 추가
    // before_data 가 null 인 경우, 가장 뒤에 추가
    // before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    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);
            this.tail = this.tail.next;
        } else {
            NodeBi cur = this.head;
            NodeBi pre = cur;
            while (cur != null) {
                if (cur.data == beforeData) {
                    if (cur == this.head) {
                        this.head = new NodeBi(data, this.head, null);
                        this.head.next.prev = this.head;
                    } 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();
    }

    //  연결 리스트의 모든 데이터 출력 (tail 부터)
    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();
    }

}

유형3. 원형 연결 리스트

https://t1.daumcdn.net/cfile/tistory/993C183B5BFAA53448

- 이전의 연결리스트들은 마지막 노드가 NULL을 가리킴

- 원형 연결리스트의 경우, 마지막 노드가 첫 번째 노드를 가리킨다.

- 사실 상, 머리와 꼬리의 구분이 없다고 생각하면 된다.

class CircularLinkedList {
    NodeBi head;
    NodeBi tail;

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

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

    // 연결 리스트에 데이터 추가
    // 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 {
            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;
                    this.head = cur.next;
                    this.tail.next = this.head;
                } else if (cur == this.tail) {
                    pre.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);
    }
}

728x90

'자료구조' 카테고리의 다른 글

[자료구조] 데크 (0)	2022.08.16
[자료구조] 큐 (0)	2022.08.13
[자료구조] 스택 (0)	2022.08.13
[자료구조] 조합 (0)	2022.08.08
[자료구조] 순열 (0)	2022.07.10

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[자료구조] 연결리스트

연결리스트 (LinkedList)란?

[ 데이터 추가 ]

[ 데이터 삭제 ]

유형1. 단순 연결 리스트

유형2. 양방향 연결 리스트

유형3. 원형 연결 리스트

'자료구조' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역