컬렉션 프레임워크 - LinkedList

Node와 연결 1

배열 리스트 단점
배열 리스트는 내부에 배열을 사용해서 데이터 보관

-> 배열의 사용하지 않는 공간 낭비

-> 배열의 중간 데이터 추가

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼 메모리를 확보, 앞이나 중간 데이터를 추가하거나 삭제할때 효율적 자료구조 -> Node

 public class Node {
 Object item;
 Node next;
 }

노드 클래스는 내부에 저장할 데이터인 item, 다음으로 연결할 참조값이 저장되는 next

1) 노드에 데이터 A 추가

2) 노드에 데이터 B 추가

Node 인스턴스를 생성하고 item에 "B"를 넣는다.
Node next 필드에 새로 만든 노드 참조값 넣어준다.

3) 노드에 데이터 C 추가

public class Node {
    Object item;
    Node next;

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

//    @Override
//    public String toString() {
//        return "Node{" +
//                "item=" + item +
//                ", next=" + next +
//                '}';
//    }

public class NodeMain1 {
    public static void main(String[] args) {
        //노드 생성하고 연결하기 A -> B -> C
        Node first = new Node("A");
        first.next = new Node("B"); //first가 가지고 있는 next에 B가 들어있는 Node 참조값 연결
        first.next.next = new Node("C"); //first가 가지고 있는 next에 C가 들어있는 Node 참조값 연결

        System.out.println("모든 노드 탐색하기");
        Node x = first; //x에 첫번째를 놓고
        while (x != null){
            System.out.println(x.item);
            x = x.next;
        }
    }
}

 Node first = new Node("A");

Node 인스턴스 생성하고 item "A"에 넣어준다.
Node first = x01
노드의 참조값 보관

노드에 데이터 B 추가

처음 만든 노드의 next 필드에 새로 만든 노드의 참조값을 넣어준다.
이렇게하면 첫 번째 노드와 두 번째 노드가 서로 연결된다.

노드에 데이터 C 추가

두 번째 만든 노드의 Node next 필드에 새로 만든 노드의 참조값을 넣어준다.
이렇게하면 두 번째 노드와 세 번째 노드가 서로 연결된다

모든 노드 탐색

 System.out.println("모든 노드 탐색하기");
        Node x = first; //x에 첫번째를 놓고
        while (x != null){
            System.out.println(x.item);
            x = x.next;

노드와 연결 2

toString()

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        Node 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();
    }
}

package chap34.collection.link;

public class NodeMain2 {
    public static void main(String[] args) {
        //노드 생성하고 연결하기 A -> B -> C
        Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("C");

        System.out.println("연결된 노드 출력하기");
        System.out.println(first); //to String 으로 출력
    }
}

IDE toString을 사용하면, 정보는 확인 가능하지만, 한눈에 보기 힘듦

노드와 연결 3

public class NodeMain3 {
    public static void main(String[] args) {
        Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("c");

        System.out.println(first);

        //모든 노드 탐색 하기
        System.out.println("모든 노드 탐색하기");
        printAll(first);

        //마지막 노드 반환하기
        Node lastNode = getLastNode(first);
        System.out.println("lastNode = " + lastNode);

        //특정 index 노드 조회하기
        int index = 2;
        Node indexNode = getNode(first, index);
        System.out.println("indexNode = " + indexNode.item);

        //데이터 추가하기
        System.out.println("데이터 추가하기");
        add(first, "D");
        System.out.println(first);
        add(first, "E");
        System.out.println(first);
        add(first, "F");
        System.out.println(first);
    }

    private static void add(Node node, String param) {
        //우선 마지막에 연결
        Node lastNode = getLastNode(node);
        lastNode.next = new Node("param"); //마지막 노드에 연결
    }

    private static Node getNode(Node node, int index) {
        Node x = node;
        for (int i = 0; i < index; i++) { //index만큼 호출 하면 된다.
            x = x.next;
        }

        return x;
    }

    private static Node getLastNode(Node node) {
        Node x = node;
        while (x != null){
            x = x.next;
        }
        return x;
    }

    public static void printAll(Node node){
        Node x = node;
        while (x != null){
            System.out.println(x.item);
            x = x.next;
        }
    }
}

마지막 노드 조회
Node getLastNode(Node node): 마지막 노드 조회
Node.next의 참조값이 null이면 노드의 끝

특정 index 노드 조회
getNode(Node node, int index): index 특정 위치 노드 찾는다.

데이터 추가

void add(Node node, String param) {
 Node lastNode = getLastNode(node);
 lastNode.next = new Node(param);
}

직접 구현하는 연결리스트 1 - 시작

연결리스트는 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가 성능 문제 어느정도 극복 가능

리스트 자료 구조
순서가 있고 중복을 허용
MyArrayList 시리즈를 만들어보았다. 배열 리스트도, 연결 리스트도 모두 같은 리스트이다. 리스트의 내부에서 배열을 사용하는가 아니면 노드와 연결 구조를 사용하는가의 차이가 있을 뿐이다

public class MyLinkedListV1 {
    private Node first;
    private int size = 0;

    public void add(Object e) {
        Node newNode = new Node(e);
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++; //하나가 추가 되었기 때문에 사이즈 증가.
    }

    public Node getLastNode() {
        Node x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    //값 setting, 예전값 가져와야 한다.
    public Object set(int index, Object element) {
        Node x = getNode(index); //index에 대한 옛날 값 찾고
        Object oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    public 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;
        }
        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;
        }
        return -1;
    }

    public int size(){
        return size;
    }

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

Node first = 첫 노드의 위치
size = 자료 구조에 입력된 데이터 사이즈, 추가 될 때 마다 하나씩 증가

vod add (Object e)
마지막에 데이터 추가
새로운 노드를 만들고, 마지막 노드를 찾아서 새로운 노드를 마지막에 연결
노드가 하나도 없다면 새로운 노드를 만들고 first 연결

Object set(int index, Object element)
특정 위치에 있는 데이터 찾아서 변경
getNode(index) 를 통해 특정 위치에 있는 노드를 찾고, 단순히 그 노드에 있는 item 데이터를 변경한다

Object get(int index)
특정 위치 데이터 반환
getNode(index) 를 통해 특정 위치에 있는 노드를 찾고, 해당 노드에 있는 값을 반환한다.

int indexOf(Object o )
데이터를 검색하고, 검색된 위치를 반환한다.
모든 노드를 순회하면서 equals() 를 사용해서 같은 데이터가 있는지 찾는다.

public class MyLinkedListV1Main {
    public static void main(String[] args) {
        MyLinkedListV1 list = new MyLinkedListV1();
        System.out.println("데이터 추가");
        list.add("a");
        System.out.println(list);
        list.add("b");
        System.out.println(list);
        list.add("c");
        System.out.println(list);

        System.out.println("다양한 기능");
        System.out.println("list.size() = " + list.size());
        System.out.println("list.get(1) = " + list.get(1));
        System.out.println("list.indexOf(\"c\") = " + list.indexOf("c"));
        System.out.println("list.set(2, \"Z\") = " + list.set(2, "Z"));
        System.out.println(list);

        System.out.println("범위 초과");
        list.add("d");
        list.add("f");
        System.out.println(list);

//        //범위 초과, capacity가 늘어나지 않으면 예외 발생
//        list.add("f");
//        System.out.println(list);
    }
}

연결 리스트는 데이터를 추가할 때 마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제는 발생하지 않는다

연결 리스트와 빅오

Object get(int index) : O(n)
void add(Object e) : O(n)
Object set(int index, Object element) : O(n)
int indexOf(Object o) : O(n)

직접 구현하는 연결리스트 - 추가와 삭제

1. 첫 번째 위치에 데이터 추가

1. 신규 노드 생성
   
   

노드를 추가했으므로 오른쪽 노드의 index 하나씩 뒤로 밀린다.
만 연결 리스트는 새로 생성한 노드의 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다.
연결 리스트의 첫 번째 항목에 값을 추가하는 것은 매우 빠르다. O(1)로 표현할 수 있다

2. 첫 위치에 데이터 삭제

노드를 삭제했으므로 오른쪽 노드의 index 하나씩 당겨진다.
배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만 연결 리스트는 일부 참조만 변경하면 된다. 나머지 노드는 어떤 일이 일어난지도 모른다
연결 리스트의 첫 번째 항목에 값을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

3. 중간 위치에 데이터 추가

인덱스 1번의 직전 노드는 인덱스 0번 노드

노드를 추가 오른쪽 노드 index 하나씩 뒤로
O(n)의 성능이다.

• 연결 리스트는 인덱스를 사용해서 노드를 추가할 위치를 찾는데 O(n)이 걸린다.
• 위치를 찾고 노드를 추가하는데는 O(1)이 걸린다.
• 따라서 둘을 합하면 O(n)이 걸린다.

4. 중간 위치 데이터 삭제

O(n)의 성능이다.

• 연결 리스트에서 인덱스로 삭제할 항목을 찾는데 O(n)이 걸린다.
• 연결 리스트에서 항목을 삭제하는 것은 매우 빠르다. O(1)로 표현할 수 있다.

직접 구현하는 연결리스트 3 - 추가 삭제

public class MyLinkedListV2 {
    private Node first;
    private int size = 0;

    public void add(Object e) {
        Node newNode = new Node(e);
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++; //하나가 추가 되었기 때문에 사이즈 증가.
    }

    public Node getLastNode() {
        Node x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    public void add(int index, Object e){
        Node newNode = new Node(e); //신규노드 생성
        if (index == 0){
            newNode.next = first; //다음을 기존의 노드와 연결
            first = newNode;//first에 newNode가 되었다고 알려준다.

            //중간이나 뒷 부분에 들어가면
        } else {
            Node prev = getNode(index - 1); //직전 노드를 찾고
            newNode.next = prev.next; //직전 노드에 새 노드를 넣는다.
            prev.next = newNode; //직전노드 = 새 노드
        }
        size++;
    }

    //값 setting, 예전값 가져와야 한다.
    public Object set(int index, Object element) {
        Node x = getNode(index); //index에 대한 옛날 값 찾고
        Object oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    public Object remove(int index){
        Node removeNode = getNode(index); //삭제할 노드 찾고
        Object removedItem = removeNode.item; //삭제할 item 지정
        if (index == 0){
            first = removeNode.next; // 첫번째 위치에 삭제

            //first가 아닌 경우
        } else {
            Node prev = getNode(index -1); //직전 노드
            prev.next = removeNode.next; //나의 다음과 나의 직전 값을 서로 연결
        }

        //초기화
        removeNode.item = null;
        removeNode.next = null;
        size --;
        return removedItem;
    }

    public 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;
        }
        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;
        }
        return -1;
    }

    public int size(){
        return size;
    }

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

public class MyLinkedListV2Main {
    public static void main(String[] args) {
        MyLinkedListV2 list = new MyLinkedListV2();
        //마지막에 추가 O(n)
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);

        //첫 항목에 추가, 삭제
        System.out.println("첫 항목에 추가");
        list.add(0, "d"); // O(1)

        System.out.println("첫 항목 삭제");
        list.remove(0);

        //중간 항목에 추가 삭제
        System.out.println("중간 항목에 추가");
        list.add(1, "e"); //O(n)
        System.out.println(list);

        System.out.println("중간 항목에 삭제");
        list.remove(1);
        System.out.println(list);
    }
}

배열 리스트 vs 연결 리스트 사용
데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

직접 구현하는 연결리스트 4 - 제네릭 도입

public class MyLinkedListV3<E> {
    private Node<E> first;
    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node(e);
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++; //하나가 추가 되었기 때문에 사이즈 증가.
    }

    public Node<E> getLastNode() {
        Node<E> x = first;
        while (x.next != 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 = newNode;//first에 newNode가 되었다고 알려준다.

            //중간이나 뒷 부분에 들어가면
        } else {
            Node<E> prev = getNode(index - 1); //직전 노드를 찾고
            newNode.next = prev.next; //직전 노드에 새 노드를 넣는다.
            prev.next = newNode; //직전노드 = 새 노드
        }
        size++;
    }

    //값 setting, 예전값 가져와야 한다.
    public E set(int index, E element) {
        Node<E> x = getNode(index); //index에 대한 옛날 값 찾고
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    public E remove(int index){
        Node<E> removeNode = getNode(index); //삭제할 노드 찾고
        E removedItem = removeNode.item; //삭제할 item 지정
        if (index == 0){
            first = removeNode.next; // 첫번째 위치에 삭제

            //first가 아닌 경우
        } else {
            Node<E> prev = getNode(index -1); //직전 노드
            prev.next = removeNode.next; //나의 다음과 나의 직전 값을 서로 연결
        }

        //초기화
        removeNode.item = null;
        removeNode.next = null;
        size --;
        return removedItem;
    }

    public 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;
        }
        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;
        }
        return -1;
    }

    public int size(){
        return size;
    }

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

    //Node 또한 GenericType 이어야 한다.
    private static class Node<E> {
        E item;

        Node<E> next;

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

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node<E> temp = this;
            sb.append("[");
            while (temp != null) {
                sb.append(temp.item);
                if (temp.next != null) {
                    sb.append("->");
                }

                temp = temp.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

Object 로 처리하던 부분을 타입 매개변수 로 변경했다.
정적 중첩 클래스로 새로 선언한 Node 도 제네릭 타입으로 선언했다.

public class MyLinkedListV3Main {
    public static void main(String[] args) {
        MyLinkedListV3<String> list = new MyLinkedListV3<>();
        list.add("a");
        list.add("b");
        list.add("c");
        String s = list.get(0);
        System.out.println("s = " + s);

        MyLinkedListV3<Integer> integerList = new MyLinkedListV3<>();
        integerList.add(1);
        integerList.add(2);
        integerList.add(3);

        Integer integer = integerList.get(0);
        System.out.println("integer = " + integer);

    }
}