LinkedList의 구현 - Single Linked List

Single Linked List의 구현 - 계속

• 이전까지 연결 리스트의 head 또는 tail에 노드를 삽입하는 것을 구현하였다.
• 이번에는 임의의 위치를 입력받아 그곳에 노드를 삽입하는 연산과 데이터를 입력받아 그 데이터와 동일한 값을 가진 노드를 찾아 삭제하는 연산을 수행할 것이다.

 

 

임의의 위치에 노드를 삽입하는 연산

• 연결 리스트에서 임의의 위치에 노드를 삽입하기 위해서는 먼저 그 위치가 어디인지부터 파악하는 것이 먼저 수행되어야 할 것이다.
• 이는 연결 리스트의 특성을 생각해 보면 리스트를 순회하며 그 위치를 찾아야 한다. 그렇다면 그 위치에 삽입하면 될 것이다. 여기서 생각을 깊게 하지 못하면 실수가 발생한다.
  • 임의의 두 노드 사이에 노드를 추가하려면 어떤 과정이 수반되어야 하는지 생각해야 한다. 새로운 노드가 생성되고 새로운 노드의 다음 노드를 임의의 위치 다음에 존재하는 노드로 연결시켜야 한다.
  • 그리고 임의의 위치 이전에 존재하는 노드의 다음 노드를 가리키는 포인터를 새로운 노드를 가리키도록 해야한다.

삽입할 위치의 기준의 잘못된 예시

• 만약 삽입할 노드의 위치를 위 사진과 같이 지정했다고 가정하자. NewNode의 다음 노드를 가리키는 포인터는 current_location을 가리키도록 하면 될 것이다.
• 하지만 이전 노드가 새로운 노드를 가리킬 수 없다. 현재 이전 노드의 위치를 모르기 때문이다. 우린 지금 단방향 연결 리스트를 구현하고 있기 때문에 이전 위치로 돌아갈 수 없다는 것을 상기해야 한다. 즉 새로운 순회를 통해 current_location의 이전 노드를 다시 찾아야 할 것이다.

삽입할 위치의 기준의 좋은 예시

• 이번에는 삽입할 위치의 이전 노드를 current_location으로 지정한 것이다. newNode의 next는 current_location의 다음 노드인 current_location.next로 지정하고 current_location의 next를 newNode로 지정하면 그림과 같이 링크가 완성된 다.
• 이런 과정을 수행하기 위해서 우리가 노드를 삽입하는데 기준이 될 위치는 우리가 삽입할 노드 위치의 이전 노드가 되어야 한다.

void addNode2Num(int data, int idx){
    Node newNode = getNode(data);
    Node start = head;

    // search location
    while(start.next != null && idx != 1){
        start = start.next;
        idx--;
    }

    newNode.next = start.next;
    start.next = newNode;
}

• 위치만 잘 잡는다면 이후는 일반적인 노드의 삽입과 동일하다.

 

 

노드의 제거 연산

• 노드의 제거는 어떻게 해야할까? 해당 노드를 가리키는 링크가 아무것도 없다면 그 노드가 리스트 상에서 제거되었다고 말할 수 있을 것이다.
• 노드의 제거 연산 역시 위치를 찾을 필요가 있다. 우리는 임의의 데이터를 받아 그 데이터와 동일한 데이터를 가진 노드를 삭제하는 연산을 구현하기로 했으므로 해당 데이터를 찾는 연산을 먼저 구현해야할 것이다.
• 해당 연산은 이미 우리가 임의의 위치에 노드를 삽입하는 연산을 구현하면서 어느 정도 구현한 감이 있는데 리스트를 순회하면서 데이터가 동일한지 찾는 것이다. 삭제 연산 역시 삭제할 노드의 이전 노드로 위치를 잡아야 한다.
• 이후는 삭제할 노드의 이전 노드의 링크를 삭제할 노드가 가리키고 있는 다음 노드를 가리키게 하는 것이다.
  
  • 이러한 방식을 사용하면 삭제할 노드의 위치를 가지고 있는 노드가 존재하지 않기 때문에 메모리상에 존재하다 JVM의 GC에 의해 할당된 메모리가 해제되게 될 것이다.
• 해당 글을 구현한 코드는 다음과 같다.

void removeNode(int data){
    Node start = head;

    while(start.next != null && start.next.data != data){
        start = start.next;
    }

    start.next = start.next.next;
    nodeCnt--;
}

 

 

 

정리

• 이렇게 단방향 연결 리스트의 구현을 알아보았다.
• 양방향 연결 리스트 역시 위와 같은 방식으로 구현이 가능하며 달라진 점은 prev라는 이전 노드를 가리키는 링크가 생김으로 인해 head나 tail에 삽입하는 연산에 생길 prev나 next에 대한 연산들에 조금 변경이 가해진다는 것이다.
• 전체적인 코드는 다음과 같다.

class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
        this.next = null;
    }
}

class LinkedList{
    private static final int MAX_NODE = 10001;
    int nodeCnt;
    Node[] nodePool;
    Node head;

    void init(){
        nodePool = new Node[MAX_NODE];
        nodeCnt = 0;
        head = new Node(-1);
    }

    Node getNode(int data){
        nodePool[nodeCnt] = new Node(data);

        return nodePool[nodeCnt++];
    }

    void addNode2Head(int data){
        Node newNode = getNode(data);

        newNode.next = head.next;
        head.next = newNode;
    }

    void addNode2Tail(int data){
        Node newNode = getNode(data);
        Node start = head;

        while(start.next != null){
            start = start.next;
        }

        start.next = newNode;
    }

    void addNode2Num(int data, int idx){
        Node newNode = getNode(data);
        Node start = head;

        while(start.next != null && idx != 1){
            start = start.next;
            idx--;
        }

        newNode.next = start.next;
        start.next = newNode;
    }

    void removeNode(int data){
        Node start = head;

        while(start.next != null && start.next.data != data){
            start = start.next;
        }

        start.next = start.next.next;
        nodeCnt--;
    }

    void printNode(){
        Node start = head.next;

        while(start != null){
            System.out.print(start.data + " ");
            start = start.next;
        }
        System.out.println();
    }

    void printArray(){
        for (int i = 0; i < nodeCnt; i++){
            System.out.print(nodePool[i].data + " ");
        }
        System.out.println();
    }
}

public class StudyCode {
    public static void main(String[] args){
        LinkedList list = new LinkedList();
        list.init();

    }
}