[자료구조] 선형 연결리스트 - 삽입, 삭제(Last)

안녕하세요. PEACE- 입니다.

자료구조 스터디 [두 번째] 글입니다.

1. 연결리스트

노드란 데이터와 다른 노드를 가리키는 공간을 가지고 있습니다.

연결리스트는 데이터 구조로써 노드간의 연결로 이뤄진 데이터 구조를 말합니다. HEAD는 첫 번째 데이터가 담긴 노드를 가리키며 연결리스트를 식별할 수 있고 연결리스트의 시작이라고 할 수 있습니다. 또한 HEAD를 통해 삽입, 삭제 기능 구현을 효율적으로 할 수 있습니다.

이러한 구조의 연결리스트를 이용해 원하는 위치에 데이터를 삽입하고 삭제하는 기능을 구현할 수 있습니다. 본 포스팅에서는 맨 앞에 데이터를 삽입하고 맨앞의 데이터를 삭제하는 기능에 대해 다루겠습니다.

2. 삽입 (Last)

맨 끝에 노드를 삽입하기 위한 방법은 아주 간단합니다. 하지만 두가지 경우를 잘 고려해 구현해야 합니다.

CASE 1 : 현재 연결리스트에 데이터가 없을 때 ( HEAD == NULL ) 

CASE 2 : 현재 연결리스트에 데이터가 있을 때 ( HEAD != NULL ) 

'CASE 1'의 경우 새로운 노드를 생성하고 HEAD가 가리키기만 하면 됩니다. 하지만 'CASE 2'의 경우에는 HEAD가 가리키는 노드의 끝에 새 노드를 연결시켜야 합니다. 방법은 이렇습니다. 반복문(Loop)를 통해 끝 노드(NEXT가 NULL인 노드)에 도달한 후 NEXT에 NEW_NODE를 참조시키는 것입니다. 

빈 연결리스트의 모습입니다.

'CASE 1'이므로 HEAD가 새 노드를 가리키도록 합니다.

'CASE 2'이므로 반복문을 통해 마지막 노드에 접근 하여 NEXT에 새 노드를 참조시킵니다.

3. 삭제 (Last)

마지막 노드를 삭제하는 방법은 아주 간단합니다. 하지만 역시 삭제에도 두 가지 상황을 고려해야 합니다.

CASE 1 : 현재 연결리스트에 데이터가 없을 때 ( HEAD == NULL ) 

CASE 2 : 현재 연결리스트에 데이터가 있을 때 ( HEAD != NULL ) 

CASE 2-1 : 데이터가 1개인 경우

CASE 2-2 : 데이터가 2개 이상인 경우

'CASE 1'의 경우는 데이터를 삭제 할 수 없으므로 조건문을 통해 삭제 작업을 수행하지 않도록 처리해야합니다. 'CASE 2'의 경우에는 파생되는 두 가지의 CASE가 존재 합니다. 첫 번째는 데이터가 1개인 경우, 두번 째는 데이터가 2개 이상인 경우입니다. 데이터가 1개인 경우에는 HEAD를 NULL로 만들어줍니다. 두번 째 경우에는 끝에서 두 번째에 있는 노드까지 이동 후 NEXT를 NULL로 만들어주어 노드의 연결을 끊어주면 됩니다.

연결리스트에 데이터가 들어있는 상태입니다.

'CASE2'이면서 데이터가 2개 이상이므로 끝에서 두번 째에 해당하는 노드에 접근하여

NEXT를 NULL로 만들어줍니다.

8이 담긴 데이터(노드)가 삭제된 연결리스트.

역시 'CASE2'에 해당하며 데이터가 한 개이므로 HEAD에 NULL을 넣어 노드를 떼어낸다. 

삭제 후

4. 소스코드

Node.class

public class Node {

    public int data;
    public Node next;

}

LinkedList.class

/* 링크드리스트
 * 1. isEmpty
 * 2. createNode
 * 3. insert [맨뒤]
 * 4. delete [맨뒤]
 * 5. diplay
 * */

public class LinkedList {

    public Node head;

    public LinkedList() {
        head = null;
    }

    public boolean isEmpty() {
        return head == null ? true : false;
    }

    private Node createNode(int data) {
        Node newNode = new Node();
        newNode.data = data;

        return newNode;
    }

    public void insertLast(int data) {
        Node newNode = createNode(data);

        if (isEmpty())
            head = newNode;
        else {
            Node pointer = head;

            while (pointer.next != null)
                pointer = pointer.next;
            pointer.next = newNode;
        }
    }

    public void deleteLast() {
        if (!isEmpty()) {
            Node pointer = head;

            if (pointer.next == null)
                head = null;
            else {
                while (pointer.next == null ? false : ( pointer.next.next == null ? false : true ) )
                    pointer = pointer.next;
                pointer.next = null;
                pointer = null;
            }
        }
    }

    public void diplay() {
        System.out.print("데이터 : ");
        if (!isEmpty()) {
            Node pointer = head;
            System.out.print(pointer.data + " ");
            while(pointer.next != null) {
                pointer = pointer.next;
                System.out.print(pointer.data + " ");
            }
        }
    }
}