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

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

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

1. 연결리스트

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

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

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

2. 삽입 (First)

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

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

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

'CASE 1'의 경우 새로운 노드를 생성하고 HEAD가 가리키기만 하면 됩니다. 하지만 'CASE 2'의 경우에는 HEAD와 HEAD가 가리키고 있는 노드 사이에 새 노드를 삽입해야 하므로 또 다른 로직이 필요합니다. 새 노드는 HEAD가 가리키고 있는 노드를 가리키고, HEAD는 새 노드를 가리키도록 하여 새 구조를 만듭니다.

HEAD가 어떠한 노드도 가리키고 있지 않을 때 입니다.

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

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

마지막으로 HEAD가 새 노드를 가리키도록 하여 연결리스트를 완성합니다.

3. 삭제

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

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

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

'CASE 1'의 경우는 데이터를 삭제 할 수 없으므로 조건문을 통해 삭제 작업을 수행하지 않도록 처리해야합니다. 반대로 'CASE 2'의 경우에는 삭제 작업을 수행하야 합니다. 삭제 방법으로 Pointer라는 HEAD와 같은 별도의 노드형 변수를 만들어서 HEAD의 NEXT를 가리키고 HEAD가 첫 번째 노드를 떼어 내고 돌아올 수 있도록 합니다.

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

Pointer라는 노드형 변수를 생성해 HEAD의 NEXT를 가리킨다.

삭제할 노드(HEAD의 NEXT)의 NEXT를 NULL로 만들어준다.

HEAD가 Pointer가 가리키는 노드를 가리키도록 한다.

Pointer를 NULL로 만들어주어 Pointer의 연결을 해제한다.

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 insertFirst(int data) {
        Node newNode = createNode(data);

        if (isEmpty())
            head = newNode;

        else {
            newNode.next = head;
            head = newNode;
        }
    }

    public void deleteFirst() {
        if (!isEmpty()) {
            Node pointer = head.next;
            head.next = null;
            head = pointer;
            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 + " ");
            }
        }
    }
}