자료구조 - 연결 리스트 Linked List

Linked List 란?

 

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

자료의 순서는 정해져 있지만, 배열과 다르게 메로리상 연속성이 보장되지는 않는다.

 

---

 

Linked List 장점 vs 단점

 

장점	단점
- 데이터 공간을 미리 할당할 필요가 없다. - 리스트의 길이가 가변적이라 데이터 추가 / 삭제가 용이하다.	- 연결구조를 위한 별도 데이터 공간이 필요하다. - 연결 정보를 찾는 시간이 필요하여 접근 속도가 상대적으로 느리다. - 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요하다.

 

---

 

Linked List 구조

 

Node -> 데이터 저장 단위로, 값과 포인터(연결 정보)로 구성되어 있다.

---

 

데이터 추가 방법

 

단방향 연결리스트

 

 

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 pre = cur;
        while (cur != null) {
            if (cur.data == beforeData) {
                if (cur == this.head) {
                    this.head = new Node(data, this.head);
                } else {
                    pre.next = new Node(data, cur);
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }
}

 

 

양방향 연결리스트

 

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

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

 

 

양방향 연결리스트

 

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