Linked List implemented by JAVA

JAVA로 구현한 링크트리스트 소스 코드는 다음과 같다.

class Node {
    Object data;
    Node next_node;

    Node(Object obj) {
        this.data = obj;
        this.next_node = null;
    }
}

Node클래스다. 기본적으로 데이터가 들어갈 부분과 Next Node로 이루어져 있으며 어떤 데이터 타입이 들어올지 모르기 때문에 Object타입으로 클래스를 정의하였다.

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;

Linked List 클래스이다. head 노드와 tail 노드, 그리고 리스트의 크기를 나타내는 변수가 있다.

기본적으로 리스트 생성 시 노드가 없는 상태의 리스트를 나타내도록 하기 위해 생성자는 기본 생성자를 사용하도록 한다.

public boolean addFirst(Object obj) {
    Node new_node = new Node(obj);
    new_node.next_node = head;
    head = new_node;

    size++;
    if(head.next_node == null)
        tail = head;

    return true;
}

새로운 노드를 추가하는 메소드로써 리스트의 가장 앞부분에 추가하는 메소드이다.

(  1  )  -  (  2  )

위의 경우 노드(1) 앞에 새로운 노드를 추가하는 것을 의미한다.

    public boolean addLast(Object obj) {
        Node new_node = new Node(obj);
        if(size == 0)
            addFirst(obj);
        else {
            tail.next_node = new_node;
            tail = new_node;
            size++;
        }

        return true;
    }

위 메소드는 리스트의 마지막에 노드를 추가하는 메소드이다. size가 0일 경우에는 addFirst와 동일한 연산을 하도록 한다.

    // Node Search to current position
    protected Node node(int index) {
        Node node = head;
        for(int i = 0; i < index; ++i) {
            node = node.next_node;
        }
        return node;
    }

이 부분은 노드를 탐색할 수 있는 메소드이다. 노드를 삭제하거나 추가 하거나 변경할 때 해당 위치의 노드로 이동하는 부분을 메소드화 하여 불필요한 중복 연산을 제거하였다.

    public boolean add(int index, Object obj) {
        if(index == 0) {
            addFirst(obj);
        } else {
            Node temp = node(index - 1);
            Node temp_next = node(index);
            Node new_node = new Node(obj);

            temp.next_node = new_node;
            new_node.next_node = temp_next;
            size++;
            if(new_node.next_node == null)
                tail= new_node;
        }

        return true;
    }

특정 위치(index)에 노드를 추가하는 메소드이다. 바로 위에서 구현한 메소드를 활용하여 노드를 탐색하고 추가할 위치의 노드에서 새로운 노드를 추가하는 과정을 구현한 모습이다.

    public boolean removeFirst() {
        Node temp = head;
        head = head.next_node;
        temp = null;
        size--;
        return true;
    }

리스트에 삽입이 있다면 제거도 있어야 하는 법! 리스트에서 가장 앞부분의 노드를 제거하는 메소드이다.

    public boolean remove(int index) {
        if(index < 0) {
            return false;
        }

        if(index == 0) {
            removeFirst();
        } else {
            Node temp = node(index - 1);
            Node del_node = temp.next_node;

            temp.next_node = temp.next_node.next_node;
            temp.next_node = null;

            if(del_node == tail)
                tail = temp;

            del_node = null;
            size--;
        }

        return true;
    }

이 메소드는 삭제를 원하는 위치(index)의 노드를 삭제하는 메소드이다.

역시 node메소드를 통해 해당 위치까지 탐색한 후 노드를 제거하는 과정을 구현한 모습이다.

 

추가로 구현해야할 사항

public boolean swap(int index_from, int index_to);

Swap 메소드를 구현을 해봐야 할 듯 하다.

생각보다 까다로울 것 같지만 구현해보고 업데이트 하도록 하겠다.

 

--> 구현을 완료하여 아래에 코드를 첨부하도록 하겠다.

	public void swapNodes(int index1, int index2){
        Node previous1 = null;
        Node previous2 = null;
        
        Node currentNode = head;
        int position = 0;
        while(null != currentNode && null != currentNode.next){
            
            if(position == index1 - 1){
                previous1 = currentNode;
            }else if(position == index2 - 1){
                previous2 = currentNode;
            }
            if(null != previous1 && null != previous2){
                break;
            }
            currentNode = currentNode.next;
            position++;
        }
        
        Node node1 = previous1.next;
        Node node2 = previous2.next;
        
        Node node1Next = node1.next;
        Node node2Next = node2.next;
        
        previous1.next = node2;
        previous2.next = node1;
        
        node2.next = node1Next;
        node1.next = node2Next;
    }