3. LinkedList 최종 코드

데이터를 임의 노드 앞에 노드를 추가하는 메서드 추가하기

 

public class DoubleLinkedList<T> {
    public static void main(String[] args) {
        DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();

        MyLinkedList.addNode(1);
        MyLinkedList.addNode(2);
        MyLinkedList.addNode(3);
        MyLinkedList.addNode(4);
        MyLinkedList.addNode(5);
        MyLinkedList.printAll();
        System.out.println("----------------");

        MyLinkedList.insertToFront(3, 2);
        MyLinkedList.printAll();
        System.out.println("----------------");

        MyLinkedList.insertToFront(6, 2);
        MyLinkedList.insertToFront(1, 0);
        MyLinkedList.printAll();
        System.out.println("----------------");

        MyLinkedList.addNode(6);
        MyLinkedList.printAll();
    }

    public Node<T> head = null;
    public Node<T> tail = null;

    public class Node<T> {
        T data;
        Node<T> prev = null;
        Node<T> next = null;

        public Node(T data) {
            this.data = data;
        }
    }
    
    public void addNode(T data) {
        if (this.head == null) {
            this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }

    public void printAll() {
        if (this.head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

    public T searchFromHead(T isData) {
        if (this.head == null) {
            return null;
        } else {
            Node<T> node = this.head;
            while (node != null) {
                if (node.data == isData) {
                    return node.data;
                } else {
                    node = node.next;
                }
            }
            return null;
        }
    }

    public T searchFromTail(T isData) {
        if (this.head == null) {
            return null;
        } else {
            Node<T> node = this.tail;
            while (node != null) {
                if (node.data == isData) {
                    return node.data;
                } else {
                    node = node.prev;
                }
            }
            return null;
        }
    }
    
    public boolean insertToFront(T existedData, T addData) {
        if (this.head == null) {
            this.head = new Node<T>(addData);
            this.tail = this.head;
            return true;
        } else if (this.head.data == existedData) {
            Node<T> newHead = new Node<T>(addData);
            newHead.next = this.head;
            this.head = newHead;
            this.head.next.prev = this.head; // 2021.09.13 추가 (prev 도 연결을 해줘야 함)            
            return true;
        } else {
            Node<T> node = this.head;
            while (node != null) {
                if (node.data == existedData) {
                    Node<T> nodePrev = node.prev;
                    
                    nodePrev.next = new Node<T>(addData);
                    nodePrev.next.next = node;
                    
                    nodePrev.next.prev = nodePrev;
                    node.prev = nodePrev.next;
                    return true;
                } else {
                    node = node.next;
                }
            }
            return false;
        }
    }
}

In [45]:

DoubleLinkedList<Integer> doubleLink = new DoubleLinkedList<Integer>();
doubleLink.main(new String[0]);

1
2
3
4
5
----------------
1
2
2
3
4
5
----------------
0
1
2
2
3
4
5
----------------
0
1
2
2
3
4
5
6

Quiz 답

• insertAfter 메서드는 새 값을 가진 노드를 생성하고, 새 노드의 next 포인터를 현재 노드의 next 포인터로 설정한 다음, 현재 노드의 next 포인터를 새 노드로 설정합니다.
• 이 구현을 사용하면, 리스트의 마지막 노드에 대해 insertAfter를 호출하면, 마지막 노드의 next 포인터가 null로 설정되기 때문에 새 노드가 리스트 끝에 삽입됩니다.

In [2]:

public class Node {
    int value;
    Node next;

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

    public void insertAfter(int value) {
        Node newNode = new Node(value);
        newNode.next = this.next;
        this.next = newNode;
    }
}

In [10]:

Node node1 = new Node(1);
Node node2 = new Node(2);
node1.next = node2;

node1.insertAfter(3);
node1.next.value;

Out[10]:

3