LinkedList의 구현 - Single Linked List

단방향 연결 리스트의 구현

• 이번에는 단방향 연결 리스트를 Java를 사용하여 구현할 것이다.
• 문제는 다음과 같다.
  • 각 명령을 문제없이 수행하는 LinkedList클래스를 작성하라
  • LinkedList 클래스는 다음과 같은 연산을 가진다.
    • 초기화
    • 리스트의 처음에 데이터 삽입
    • 리스트의 마지막에 데이터 삽입
    • 리스트의 임의의 위치에 데이터 삽입
    • data와 동일한 값을 가진 데이터를 리스트에서 삭제
  • 이때 어떠한 Java 라이브러리도 사용하면 안된다.
  • 데이터는 int형 정수 데이터로 제공되며 메서드 전체의 호출 수는 1만번을 초과하지 않는다고 가정한다.

 

 

Node의 정의

• 이전 연결 리스트의 정의와 구조에서 보았듯이 연결 리스트는 Node, head로 구성되며 Node는 데이터를 저장하는 곳과 자신의 다음 Node가 존재하는 메모리 주소를 가지고 있다고 했었다.
• 따라서 Node를 다음과 같이 클래스로 나타낼 수 있다.

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

• 문제에서 데이터는 int형 정수 데이터로 제공되기 때문에 int data로 선언하였다.
• 처음 생성될 때 자신의 다음 데이터가 무엇인지 결정되지 않았기 때문에 null로 초기화 한다.

 

 

 

LinkedList 클래스의 기본적인 구조와 메모리 풀 기법

• 우선 메모리 풀 기법이 무엇인지에 대해 살펴보자.
  • 문제의 제약사항을 보면 메서드 전체의 호출 수는 1만번을 초과하지 않는다고 가정한다. 라고 되어있다.
  • 이는 노드를 추가하는 연산만 나와도 최대 1만번까지만 나올 수 있다는 것을 의미한다. 즉 데이터 개수의 상한이 정해져 있다.
  • 그렇다면 매번 새로운 노드를 생성하여 추가하는 것 보다 1만개의 Node 배열을 생성하고 필요할 때 이 Node 배열에 저장된 Node를 꺼내면 배열의 특성상 O(1)로 접근하여 꺼낼 수 있기 때문에 동적으로 생성하는 것 보다 시간적 코스트가 적을 것이다.
  • 이렇게 데이터 개수의 상한을 알고 있을 경우에 전처리를 통해 미리 데이터 개수만큼 배열을 사용하여 최적화 하는 것을 메모리 풀 기법이라고 한다.
• 위의 메모리 풀 기법을 사용해보도록 하자. 그렇다면 미리 1만개의 Node를 가지고 있는 배열인 nodePool과 인덱싱할 수 있는 nodeCnt변수도 필요할 것이다.
• 또한 LinkedList의 첫 번째 Node를 가리키는 head도 필요하다. head는 더미 Node를 생성하고 next만 첫 번째 데이터를 가리키도록 하여 만들 수 있을 것이다.
• 그렇다면 LinkedList 클래스의 멤버 변수는 다음과 같이 만들 수 있을 것이다.

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

 

 

 

LinkedList의 초기화 및 삽입 연산

• 멤버 변수들을 정의했으니 이제 이들을 초기화해야 한다. nodePool은 가질 수 있는 최대 노드 수인 MAX_NODE만큼 가지도록 배열 초기화를 사용하고, nodeCnt는 초기에 노드가 존재하지 않기 때문에 0이 되야 할 것이다.
• head는 더미 노드를 생성하여 초기화한다.

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

 

• 삽입 연산은 3가지 종류로 문제에 정의되어 있으며 이번 게시글에는 리스트의 처음과 마지막에 데이터를 삽입하는 방법을 구현할 것이다.
• 데이터를 추가하려면 어떻게 해야할까. 이는 그림으로 생각해 보면 방법이 쉽게 생각날 수 있다.

연결 리스트에서의 데이터 추가

 

• 데이터를 리스트의 처음에 넣는 경우이다 새로운 노드를 생성한다. 이후 1번을 먼저 해야할까 아님 2번을 먼저 해야할까?
• 잠시 생각해보면 당연하게도 1번이 선행되어야 한다. 왜냐하면 2번을 먼저 수행할 시, 원래 가지고 있던 노드들을 모두 잃어버리게 되기 때문이다. 위 사진에서 2번을 먼저 수행할 경우 첫 번째 Node의 주소값을 유일하게 알고 있는 변수인 next가 New Node의 주소로 새롭게 덧씌워져 버리기 때문에 원래의 노드 주소는 어디에서도 찾을 수 없게 된다. 이는 곧 자료의 유실로 이어진다.
• 따라서 이를 방지하기 위해 1번을 먼저 수행하여 New Node의 next가 원래 리스트의 첫 번째 노드 주소를 가지도록 한다. 이렇게 하면 head에서 New Node의 주소를 next에 덧씌워도 New Node의 next가 존재하기 때문에 자료의 유실이 발생하지 않는다.
• 따라서 리스트의 맨 처음에 데이터를 삽입하는 경우 다음과 같은 순서로 삽입한다.
  • 새로운 노드를 생성한다.
  • 새로운 노드의 next를 head가 가리키고 있는 노드(비어있다면 null)로 설정한다.
  • head의 next를 새로운 노드로 설정한다.
• 위 알고리즘을 코드로 구현하면 다음과 같다.

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

• getNode 메서드는 메모리 풀 기법을 사용해 생성한 노드를 반환하는 메서드이다. 그 이외에는 알고리즘을 그대로 구현한 것이다.
• 다음은 리스트의 마지막에 새로운 노드를 추가하는 경우이다.

연결 리스트에서의 데이터 추가 2

• 마지막에 추가하는것은 매우 쉽다. 마지막 노드의 next를 New Node로 설정하면 된다.
• 하지만 어떤 노드가 마지막 노드인가를 먼저 판단해야 한다. 어떤 노드가 마지막 노드인지 판단하기 위해서는 어떤 조건이 필요할까?
• 연결 리스트에 대해 조금 생각해 보면 금방 알 수 있다. 어떤 노드가 마지막 노드인지 판단하기 위해서는 어떤 노드의 next 값이 null인지 확인하면 된다. 왜냐하면 마지막 노드를 제외한 모든 노드의 next는 자신의 다음 노드를 가리키고 있을 것이기 때문이다.
• 따라서 head부터 시작하여 각 노드들을 순회하면서, 각 노드의 next가 null인지를 검사한 뒤 null이라면 순회를 종료하고 해당 노드에서 삽입 연산을 진행하면 된다. 따라서 알고리즘을 다음과 같이 정의할 수 있다.
  • 새로운 노드 New Node를 생성한다.
  • 리스트의 head에서부터 시작하여 노드의 next가 null일때 까지 각 노드를 순회한다.
  • next가 null인 노드의 next를 New Node로 설정한다.
• 해당 알고리즘을 구현한 코드는 다음과 같다.

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

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

    start.next = newNode;
}

 

 

 

정리

• 지금까지 LinkedList의 구조 정의와 리스트의 앞에 추가, 끝에 추가를 구현해 보았다. 이제 남은 것은 임의의 위치에 노드를 추가하는 것과 입력받은 데이터와 동일한 데이터를 가진 노드를 삭제하는 것만 남았다.
• 지금까지 구현한 코드의 종합적인 모습은 다음과 같다.

class Node{
    int data;
    Node next;

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

public class StudyCode{
    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;
    }
}