kingsubin

LinkedList 본문

Algorithm

LinkedList

kingsubin 2020. 8. 31. 16:36
public class Node<T> {

    public T data;
    public Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}
public class MySingleLinkedList<T> {

    public Node<T> head = null;
    public int size = 0;

    public MySingleLinkedList() {}

    public void addFirst(T item) {
        Node<T> newNode = new Node<T>(item);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void addAfter(Node<T> before, T item) {
        Node<T> newNode = new Node<T>(item);
        newNode.next = before.next;
        before.next = newNode;
        size++;
    }

    // 연결리스트의 index번째 위치에 새로운 데이터를 삽입한다.
    public void add(int index, T item) {
        if (index < 0 || index > size) {
            return; // 추후에 throw
        }
        if (index == 0) {
            addFirst(item);
        } else {
            Node<T> node = getNode(index - 1);
            addAfter(node, item);
        }
    }

    public T removeFirst() {
        if (head == null) {
            return null;
        } else {
            T temp = head.data;
            head = head.next;
            size--;
            return temp; // 삭제된 데이터 리턴
        }
    }

    public T removeAfter(Node<T> before) {
        if (before.next == null) {
            return null;
        } else {
            T temp = before.next.data;
            before.next = before.next.next;
            size--;
            return temp; // 삭제된 데이터 리턴
        }
    }

    // index 번째 노드를 삭제하고, 그 노드에 저장된 데이터 반환
    public T remove(int index) {
        if (index < 0 || index >= size) {
            return null;
        } else if (index == 0) {
            return removeFirst();
        } else {
            Node<T> prev = getNode(index - 1);
            return removeAfter(prev);
        }
    }

    // item 을 가진 노드를 찾아 삭제한다. 삭제된 노드에 저장된 값을 리턴
    public T remove(T item) {
        Node<T> p = head;
        Node<T> q = null;
        while ( p!= null && !p.data.equals(item)) {
            q = p;
            p = p.next;
        }

        if (p == null) { // 삭제할 노드가 존재하지 않는 경우, LinkedList가 empty일 경우
            return null;
        }
        if (q == null) {
            return removeFirst(); // 찾고있는 노드가 첫 번째 노드일 경우
        } else {
            return removeAfter(q); // 일반적인 경우
        }
    }

    // 검색
    public int indexOf(T item) {
        Node<T> p = head; // 임시값
        int index = 0;

        while (p != null) {
            if (p.data.equals(item)) {
                return index;
            }
            p = p.next;
            index++;
        }
        return -1;
    }

    // 연결리스트의 index번째 노드의 주소를 반환한다 .
    public Node<T> getNode(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    // index번째 노드에 저장된 데이터를 반환한다.
    public T get (int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p.data;
        // return getNode(index).data; 로 표현가능
        // 이렇게 사용 할 경우 위에 if문은 필요하다
    }


}

 

 

 


※참조

www.youtube.com/watch?v=3BMnWg5k0fU&list=PL52K_8WQO5oWz_LYm3xg23m5q9qJXoE4n&index=39

'Algorithm' 카테고리의 다른 글

트리 정리  (0) 2020.09.07
그리디&구현, DFS&BFS  (0) 2020.09.01
EOF (End of File)  (0) 2020.08.29
정렬 정리  (0) 2020.08.27
검색 정리  (0) 2020.07.13
0 Comments
댓글쓰기 폼