Java Mid 16 - Collection LinkedList 구현하기

LinkedList

LinkedList의 기본 개념

노드(Node):
- 데이터와 다음 노드에 대한 참조(링크)를 포함하는 객체다.
- 각 노드는 다음 노드의 주소를 저장하여 체인처럼 연결된다.
링크(Link):
- 노드 간의 연결을 나타내며, 하나의 노드가 다른 노드를 가리킨다.
- *단일 연결 리스트(Singly Linked List)는 각 노드가 **하나의 참조만 가지고 다음 노드를 가리킨다.
- *이중 연결 리스트(Doubly Linked List)는 각 노드가 **이전 노드와 다음 노드를 모두 가리킬 수 있다.

LinkedList의 주요 특징

동적 크기 조정:
- 노드 기반으로 되어 있어, 데이터의 개수가 변해도 동적으로 크기가 조정된다.
삽입 및 삭제:
- 노드의 연결만 변경하면 되므로, 삽입과 삭제가 빠르다.
- 특정 위치에 노드를 삽입하거나 삭제할 때 O(1)의 시간 복잡도로 수행할 수 있다.
순차 접근:
- 특정 위치의 데이터를 찾으려면 처음부터 순차적으로 탐색해야 하므로 O(n)의 시간 복잡도를 가진다.
- 랜덤 접근이 불가능하며, 데이터를 검색하려면 처음부터 끝까지 순차적으로 접근해야 한다.
메모리 사용:
- 각 노드는 데이터 외에도 참조를 저장하므로, 배열보다 메모리 사용이 비효율적일 수 있다.

LinkedList 구현하기

package collection.link;

public class MyLinkdeListV1 {

    private Node first;
    private int size;

    //기능추가
    public void add(Object e) {
        Node newNode = new Node( e );
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node getLastNode() {
        Node x = first;
        while (x.next != null) { //null이 아닐 때 까지 계속 순회함
            x = x.next;
        }
        return x;
    }

    public Object set(int index, Object element) {
        Node x = getNode( index );
        Object oldValue = x.item; //엣날 값 넣어주고
        x.item = element; // 새 값 넣어주고
        return oldValue; // 옛날 값 반환
    }

    Object get(int index) {
        Node node = getNode( index );
        return node.item;
    }

    private Node getNode(int index) {
        Node x= first;
        for(int i = 0; i < index; i++){
            x = x.next; //3이면 3번 이동해서 3의 인덱스를 찾는다.
        }
        return x;
    }

    public int indexOf(Object o) {
        int index = 0;
        for (Node x = first; x != null; x = x.next) {
            if (o.equals( x.item )) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkdeListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

}

배열리스트는 중간에 데이터를 추가하거나 삭제할 때 데이터를 한칸씩 밀어 넣어야 한다는 단점이 있었지만 리스트는 이 문제를 해결할 수 있다.

제네릭 타입으로 만들기

package collection.link;

public class MyLinkdeListV3<E> {

    private Node<E> first;
    private int size;

    //기능추가
    public void add(E e) {
        Node<E> newNode = new Node( e );
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node<E> getLastNode() {
        Node<E> x = first;
        while (x.next != null) { //null이 아닐 때 까지 계속 순회함
            x = x.next;
        }
        return x;
    }

    //추가코드
    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);
        if (index == 0) {
            newNode.next = first; //기존에 first에다가 next를 넣어준다음
            first = newNode; //새로운 노드를 first에 넣어준다.
        } else {
            Node<E> prev = getNode( index - 1 );
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

    public Object set(int index, E element) {
        Node<E> x = getNode( index );
        E oldValue = x.item; //엣날 값 넣어주고
        x.item = element; // 새 값 넣어주고
        return oldValue; // 옛날 값 반환
    }

    //추가코드
    public E remove(int index) {
        Node<E> removeNode = getNode( index );
        E removeItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node prev = getNode( index - 1 );
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removeItem;
    }

    E get(int index) {
        Node<E> node = getNode( index );
        return node.item;
    }

    private Node<E> getNode(int index) {
        Node<E> x= first;
        for(int i = 0; i < index; i++){
            x = x.next; //3이면 3번 이동해서 3의 인덱스를 찾는다.
        }
        return x;
    }

    public int indexOf(E o) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals( x.item )) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkdeListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    //중첩 클래스 만들기
    private static class Node<E> {

        E item;
        Node next;

        public Node(E item) {
            this.item = item;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(); //loop에서 문자를 떠할 땐 stringBuilder가 좋다.
            Node<E> x = this;
            sb.append( "[" );
            while (x != null) {
                sb.append( x.item );
                if (x.next != null) {
                    sb.append( "->" );
                }
                x = x.next;
            }
            sb.append( "]" );
            return sb.toString(); //command optN
        }
    }
}

제네릭을 도입후 타입안정성 마저 보장할 수 있다.

Reference

인프런 김영한님의 자바강좌 + 나의 뇌