[자료구조] 연결 리스트 - (단일, 이중, 원형)(Linked List)

연결 리스트란?

노드(데이터 + 다음 노드 주소)를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

장점	단점
노드 (추가, 삭제)시간복잡도가 O(1) 입니다.	노드 (탐색) 시간복잡도가 O(n) 입니다.

 

문제 1: O(1) 이란 어느 정도의 시간복잡도 인지?

문제 2: O(n) 이란 어느 정도의 시간복잡도 인지?

 

연결 리스트의 종류

 - 단일 연결 리스트 

 - 이중 연결 리스트

 - 원형 연결 리스트

 

단일 연결리스트란?

  - 탐색을 우측으로 가는 단방향 탐색만 가능합니다.

  - 단점으로 마지막 노드에서 좌측으로 탐색하는 역방향 탐색이 불가능합니다.

  - Data Field : 데이터

  - Link field : 다음 노드의 주소

 

그림1) 연결리스트 형태

 

단일 연결 리스트 (삽입) 

 

그림1) 연결리스트 삽입(데이터가 1개도 없는 경우)

 

그림2) 연결리스트 삽입(데이터가 있는 경우 & 가장 마지막에 삽입시)

 

그림3) 연결리스트 중간에 insert

 

단일 연결 리스트 (삭제)

 

 

단일 연결 리스트 구현 

class LinkedList<T> {
    private ListNode head = null;

    public void insert(ListNode preNode, T data) {
        preNode.link = new ListNode<>(data, preNode.link);
    }

    public void insert(T data) {
        ListNode<T> newNode = new ListNode<>(data, null);

        if (head == null) {
            this.head = newNode;
        } else {
            ListNode tempNode = head;

            while (tempNode.link != null) {
                tempNode = tempNode.link;
            }

            tempNode.link = newNode;
        }
    }

    public void delete(T data) {
        ListNode preNode = head;
        ListNode tempNode = head.link;

        if (data.equals(preNode.getData())) {   //삭제하려는 데이터와 현재 노드 데이터와 일치하는 경우
            head = preNode.link;
            preNode.link = null;
        } else {
            while (tempNode != null) {
                if (data.equals(tempNode.getData())) {
                    if (tempNode.link == null) {
                        preNode.link = null;
                    } else {
                        preNode.link = tempNode.link;
                        tempNode.link = null;
                    }
                    break;
                } else {
                    preNode = tempNode;
                    tempNode = tempNode.link;
                }
            }
        }
    }

    public void lastDelete() {
        ListNode preNode;
        ListNode tempNode;

        if (head == null) {
            return;
        }

        if (head.link == null) {
            head = null;
        } else {
            preNode = head;
            tempNode = head.link;

            while (tempNode.link != null) {
                preNode = tempNode;
                tempNode = tempNode.link;
            }

            preNode.link = null;
        }
    }

    public ListNode search(T data) {
        ListNode tempNode = this.head;

        while (tempNode != null) {
            if (data == tempNode.getData()) {
                return tempNode;
            } else {
                tempNode = tempNode.link;
            }
        }

        return tempNode;
    }


    public void print() {
        ListNode tempNode = this.head;

        while (tempNode != null) {
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.link;
        }
    }
}

 

이중 연결 리스트란?

  - 우측 탐색만 가능한 단방향 탐색과는 달리 양방향 탐색이 가능합니다.

  - Data Field : 데이터

  - Next Link field : 다음 노드의 주소

  - Prev Link field : 이전 노드의 주소

 

 

 

원형 연결 리스트란?

  - 단일 연결리스트와 동일한 구조에서 아래와 같이 변경되었습니다.
    1. Head가 사라지고 Tail이 추가되었습니다. 
    2. 마지막 노드가 첫 노드를 가르킵니다.

  - Data Field : 데이터

  - Link field : 다음 노드의 주소

  - Tail : 마지막 노드

* 삽입,삭제가 단일 연결 리스트와 동일한 구조로 그림은 생략 되었습니다.