LinkedList 구현 방법 (MyLinkedList)

✨  Constructor & Basic Attribute

private Node head;
private Node tail;
private int size;

private class Node{
    private int value;
    private Node next;

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

    public String toString() {
        return String.valueOf(this.value);
    }
}

제일 앞에 있는 노드, 뒤에 있는 노드, size를 정의한다. 또한 노드를 내부 class로 생성하여 contructor로 객체 생성 시 초기화할 수 있도록 한다.

 

 

✨ addFirst(int data)

public void addFirst(int data) {
    Node newNode = new Node(data);
    // 기존의 head를 다음 node로 지정
    newNode.next = head;
    head = newNode;
    size++;
    if(head.next == null) {
        tail = head;
    }
}

 코드를 공부하는데 완벽하게 이해가 가지 않아서 그림을 그려 이해를 하려고 노력했다.

addFirst를 하기 전에는 첫 번째 파란색 동그라미가 Head 였다. newNode가 head가 되기 이전에, newNode의 next에 head의 정보를 두고 newNode를 head로 지정한다. 이때, head = newNode를 진행하고, newNode.next = head를 진행하면 next의 값이 무엇인지 알 수 없다.

 

✨ addLast(int data)

public void addLast(int data) {
    Node newNode = new Node(data);
    // 처음으로 값을 넣는다면
    if(size == 0) {
        addFirst(data);
    }else {
        tail.next = newNode;
        tail = newNode;
        size++;
    }
}

 

만약 첫 번째로 Node의 값을 넣는 것이라면 addFirst 함수로 값을 넣고, 노드의 값이 실제로 있는 채로 값을 넣는다면 마지막 노드의 next를 newNode로 한다. 그 후, tail node를 newNode로 선언하면 된다.

 

 

✨ add(int index, int data)

public void add(int index, int data) {
    if(index ==0) {
        addFirst(data);
    }else {
        Node x = node(index-1); // index 2에 넣고 싶다면 index 1의 node
        if(x == null) {
            return;
        }
        Node y = x.next; // 원래 index 2 node

        Node newNode = new Node(data);
        x.next = newNode;
        newNode.next = y;
        size ++;

        if(newNode.next == null) {
            tail = newNode;
        }
    }
}

// 외부에서 사용하면 안됨.
private Node node(int index) {
    Node x = head;
    for(int i = 0; i<index ;i++	) {
        x = x.next;
        if(x == null) {
            return null;
        }
    }
    return x;
}

원하는 index로 data를 add 하기 위해서는 index에 위치한 node가 무엇인지 알아야 한다. 이 때 사용하는 함수가 node(int index)이다. 이 함수는 외부에서 사용하면 안되기 때문에 public을 붙여주지 않는다.

node(int index)는 node를 head부터 차례대로 index의 값까지 값을 불러오고 node를 return 해준다. 

 

add(int index, int data)에서 index가 0이면 addFirst를 사용하고, 아니면 위의 코드대로 진행한다.

 

 

✨ toString()

public String toString() {
    String str = "";
    Node temp = head;

    while(temp.next!=null) {
        str += temp.value + ", ";
        temp = temp.next;
    }
    str += temp.value;
    return str;
}

 

✨ remove

1. removeFirst()

2. remove(int index)

3. removeLast()

public int removeFirst() {
    if(head == null) {
        return -1;
    }

    Node temp = head;
    head = head.next;
    int returnData = temp.value;
    temp = null;
    size --;

    return returnData;
}


public int remove(int index) {
    if(index == 0) {
        return removeFirst();
    }else if(node(index-1) == null) {
        return -1;
    }
    else{
        Node x = node(index-1);
        Node y = x.next; // 삭제할 노드

        x.next = y.next;
        int returnData = y.value;

        if(y == tail) {
            tail = x;
        }
        y = null;
        size--;
        return returnData;
    }

}

public int removeLast() {
    return remove(size-1);
}

 

 

✨ size() & get()

public int size() {
    return size;
}

public int get(int index) {
    return node(index).value;
}

 

✨ indexOf

public int indexOf(int data) {
    Node temp = head;
    int index = 0;
    while(head.value != data) {
        temp = temp.next;
        index ++;
        if(temp == null) { // data의 값이 없다면
            return -1;
        }
    }
    return index;
}

 

 

✨ ListIterator next, hasNext

//main.class
MyLinkedList.MyListIterator listIterator = numbers.listIterator();

//MyLinkedList.MyListIterator.class
public class MyListIterator{
    private Node next;
    private Node lastReturned;
    private int nextIndex;

    public MyListIterator() {
        this.next = MyLinkedList.this.head;
        this.nextIndex = 0;
    }

    public int next() {
        this.lastReturned = this.next;
        this.next = this.next.next;
        this.nextIndex ++;
        return lastReturned.value;
    }

    public boolean hasNext() {
        return nextIndex < size();
    }

}

 

previous 노드는 값을 알 수 없는데, 그 이유는 노드는 한 방향으로 이동하기 때문이다.

양방향으로 알기 위해서는 double linkedList를 공부해야 한다.

 

✨ ListIterator add

public void add(int data) {
    Node newNode = new Node(data);
    if(lastReturned == null) {
        head = newNode;
        newNode.next = this.next;
    } else {
        lastReturned.next = newNode;
        newNode.next = this.next;
    }	

    lastReturned = newNode;
    nextIndex++;
    size ++;

}

 

 

✨ ListIterator remove

public void remove() {
    if(nextIndex == 0) {
        throw new IllegalStateException();
    }
    MyLinkedList.this.remove(nextIndex-1);
    nextIndex--;
}

기존 remove 코드를 사용해서, node 함수가 실행되므로 실용적인 코드는 아니다.