김영한의 실전 자바 - 중급 2편 - Sec 05. 컬렉션 프레임워크 - LinkedList

목차

1. 포스팅 개요
2. 본론
    2-1. 노드와 연결1
    2-2. 노드와 연결2
    2-3. 노드와 연결3
    2-4. 직접 구현하는 연결 리스트1 - 시작
    2-5. 직접 구현하는 연결 리스트2 - 추가와 삭제1
    2-6. 직접 구현하는 연결 리스트3 - 추가와 삭제2
    2-7. 직접 구현하는 연결 리스트4 - 제네릭 도입
3. 요약

1. 포스팅 개요

해당 포스팅은 김영한의 실전 자바 중급 2편 Section 5의 컬렉션 프레임워크 - LinkedList 에 대한 학습 내용이다.

학습 레포 URL : https://github.com/SsangSoo/inflearn-holyeye-java-mid2
(해당 레포는 완강시 public으로 전환 예정이다.)

2. 본론

2-1. 노드와 연결1

배열 리스트의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다.
따라서 다음과 같은 단점을 가진다.

• 배열의 사용하지 않는 공간 낭비
• 배열에 데이터를 추가 및 삭제시 공간확보를 위해 데이터의 이동을 해야 한다.

노드와 연결

• 노드를 만들어서 각 노드를 서로 연결하는 방식이다.
• 낭비되는 메모리 없이 필요한 만큼만 메모리를 확보하여 사용한다.
• 앞이나 중간에 데이터를 추가하거나 삭제할 때 효율적인 자료 구조

노드 클래스

public class Node {
    Object item;
    Node next;
}

노드 클래스는 내부에 저장할 데이터인 item과, 다음으로 연결할 노드의 참조인 next를 가진다.

노드 클래스를 사용해서 데이터를 순서대로 연결하는 과정

노드 그림

• 처음에 노드에 A 데이터를 넣는다.

연결 과정

• A 데이터가 들어있는 노드에 B 를 넣은 노드를 next 로 연결시킨다.
• B 데이터가 들어있는 노드에 C 를 넣은 노드를 next 로 연결시킨다.

코드로 구현

• 노드

public class Node {  

    Object item;  
    Node next;  

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

참고로 설명을 단순히 하기위해 필드 접근제어자는 private이 아니라, 디폴트로 선언했다.

사용 예제다.

public class NodeMain1 {  
    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("모든 노드 탐색하기");  
        Node x = first;  
        while (x != null) {  
            System.out.println(x.item);  
            x = x.next;  
        }
    }  
}

// 결과
모든 노드 탐색하기
A
B
C

• Node x 는 처음 노드부터 순서대로 이동하면서 모든 노드를 가리킨다.
• 처음에 Node x 는 A를 가진 노드를 참조한다.
• 그리고 while 문을 통해 반복해서 다음 노드를 가리킨다.
• while 문은 다음 노드가 없을 때 까지 반복한다.
• Node.next 의 참조값이 null 이면 노드의 끝이다.

2-2. 노드와 연결2

노드의 연결 상태를 더 편하게 보기 위해 toString() 을 오버라이딩 해보자.
IDE의 도움을 받자.

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 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);  

    }  
}

// 결과
연결된 노드
Node{item=A, next=Node{item=B, next=Node{item=C, next=null}}}

확인하기 복잡하므로 [A->B->C] 처럼 필요한 정보만 편리하게 확인할 수 있게 toString() 을 직접 구현해보자.

public class Node {  

    Object item;  
    Node next;  

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

 /*  
    // IDE 생성 toString()    
    @Override    
    public String toString() {        
        return "Node{" +                
            "item=" + item +                
            ", next=" + next +                
            '}';    
    } 
*/  
    // [A->B->C]    
    @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();  
    }  
}

실핼결과는 다음처럼 바뀐다.

// 결과
연결된 노드
Node{item=A, next=Node{item=B, next=Node{item=C, next=null}}}

// toString 새로 만든 후 결과
연결된 노드
[A -> B -> C]

2-3. 노드와 연결3

노드와 연결을 활용해서 다음과 같은 기능을 만든다.

• 모든 노드 탐색
• 마지막 노드 조회
• 특정 index의 노드 조회
• 노드에 데이터 추가하기

public class NodeMain3 {  
    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(first);  

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

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

        // 특정 index의 노드 조회하기  
        int index = 2;  
        Node index2Node = getNode(first, 2);  
        System.out.println("index2Node = " + index2Node.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 printAll(Node node) {  
        Node x = node;  
        while (x != null) {  
            System.out.println(x.item);  
            x = x.next;  
        }  
    }  

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

    private static Node getNode(Node node, int index) {  
        Node x = node;  
        for(int i = 0; i < index; i++) {  
            x = x.next;  
        }  
        return x;  
    }  

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

// 결과
[A -> B -> C]
모든 노드 탐색하기
A
B
C
lastNode = [C]
index2Node = C
데이터 추가하기
[A -> B -> C -> D]
[A -> B -> C -> D -> E]
[A -> B -> C -> D -> E -> F]

정리

• 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
• 지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결(Link, 링크) 되어 있다.
• 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다.
  • 배열과 다르게 메모리를 낭비하지 않는다.
  • next 필드를 통해 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
• 각각의 노드를 연결(링크)해서 사용하는 자료 구조로 리스트를 만들 수 있는데, 이를 연결 리스트라고 한다.

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

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

참고로 리스트(List) 자료 구조는 다음과 같다.

• 순서가 있다.
• 중복을 허용한다.

연결 리스트를 직접 구현해보자.

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++;  

    }  

    private Node getLastNode() {  
        Node x = first;  
        while(x.next != 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;  
    }  

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

    public int size() {  
        return size;  
    }  

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

사용 예시는 다음과 같다.

public class MyLinkedListV1Main {  
    public static void main(String[] args) {  
        MyLinkedListV1 list = new MyLinkedListV1();  
        System.out.println("== 데이터 추가==");  
        System.out.println(list);  
        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");  
        System.out.println(list);  
        list.add("e");  
        System.out.println(list);  
        list.add("f");  
        System.out.println(list);  
    }  
}

// 결과
== 데이터 추가==
MyLinkedListV1{first=null, size=0}
MyLinkedListV1{first=[a], size=1}
MyLinkedListV1{first=[a -> b], size=2}
MyLinkedListV1{first=[a -> b -> c], size=3}
==기능 사용==
list.size() = 3
list.get(1) = b
list.indexOf("c") = 2
list.set(2, "z") = c
MyLinkedListV1{first=[a -> b -> z], size=3}
== 범위 초과==
MyLinkedListV1{first=[a -> b -> z -> d], size=4}
MyLinkedListV1{first=[a -> b -> z -> d -> e], size=5}
MyLinkedListV1{first=[a -> b -> z -> d -> e -> f], size=6}

• ArrayList 를 학습할 떄 작성했던 코드를 그대로 썼다.

연결 리스트와 빅오

• Object get(int index)
  • 특정 위치에 있는 데이터를 반환한다.
  • O(n)
    • 연결 리스트에서 사용하는 노드들은 배열이 아니다.
      • 단지 다음 노드에 대한 참조가 있을 뿐이다.
    • 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자 만큼 다음 노드를 반복해서 찾아야 한다.
    • 인덱스 조회 성능이 나쁘다.
    • 특정 위치의 노드를 찾는데 O(n)이 걸린다.
• void add(Object e)
  • 마지막에 데이터를 추가한다.
  • O(n)
    • 마지막 노드를 찾는데 O(n)이 소요된다.
    • 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서 O(n)이다.
• Object set(int index, Object element)
  • 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
  • O(n)
    • 특정 위치의 노드를 찾는데 O(n)이 걸린다.
• int indexOf(Object o)
  • 데이터를 검색하고, 검색된 위치를 반환한다.
  • O(n)
    • 모든 노드를 순회하면서 equals() 를 사용해서 같은 데이터가 있는지 찾는다.

정리

• 연결 리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용한다.
  • 배열 리스트의 단점인 메모리 낭비를 해결할 수 있었다.
  • 물론 연결을 유지하기 위한 추가 메모리가 사용되는 단점도 함께 존재한다.

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

배열 리스트는 중간에 데이터를 추가하거나 삭제할 때 기존 데이터를 한 칸씩 이동해야 하는 문제가 있었다.
연결 리스트는 이 문제를 어떻게 해결하는지 알아본다.

특정 위치에 있는 데이터를 추가하고, 삭제하는 기능을 만든다.
다음 두 기능을 추가하면 된다.

void add(int index, Object e)

• 특정 위치에 데이터를 추가한다.
• 내부에서 노드도 함께 추가된다.

Object remove(int index)

• 특정 위치에 있는 데이터를 제거한다.
• 내부에서 노드도 함께 제거된다.

• 첫 번째 위치의 데이터 추가
  • 신규 노드를 만들어서 참조만 첫 번째 노드를 참조하게 하면 된다.
  • O(1)

최종 결과

• 첫 번째 위치의 데이터 삭제
  • 원래 가리키던 노드를 제거하고, 그 다음 대상의 노드를 참조하게 하면 된다.
  • 그리고 삭제 대상 노드가 가진 값들을 다 null로 초기화 해준다.
  • O(1)

3. 삭제 대상의 데이터 초기화

• 중간 위치에 데이터 추가
  • 새로운 노드를 생성하고, 노드가 입력될 위치의 직전 노드(prev)를 찾아둔다.
  • 직전 노드는 원래 참조하고 있던 노드에서 신규 노드를 참조하게 하고, 신규 노드는 직전 노드가 원래 참조하고 있던 노드를 참조하게 한다.
  • O(n) 이다.
    • 노드를 추가할 위치를 찾는데, O(n) 이 위치를 찾고 노드를 추가하는데 O(1)이 걸린다.

1. 새로운 노드를 생성하고, 노드가 입력될 위치의 직전 노드(prev)를 찾아둔다.

2. 신규 노드와 다음 노드를 연결한다. 직전 노드(prev)의 다음 노드를 연결하면 된다.

3. 직전 노드(prev)에 신규 노드를 연결한다

최종 결과

• 중간 위치에 데이터 삭제
  • 삭제할 대상 노드를 찾고, 삭제 대상의 직전 노드를 찾아둔다.
  • 삭제 대상의 직전 노드가 삭제할 대상 노드가 참조하는 노드를 참조하게 한다.
  • O(n)이다.
    • 삭제할 항목을 찾는데 O(n)이 걸리고, 항목을 삭제하는 것은 O(1) 이 걸린다.

1. 삭제 대상을 찾는다. 그리고 삭제 대상의 직전 노드(prev)도 찾아둔다.

2. 직전 노드(prev)의 다음 노드를 삭제 노드의 다음 노드와 연결한다.

3. 삭제 노드의 데이터를 초기화 한다.

최종 결과

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

직접 구현해보자.

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 void add(int index, Object e) {  
        Node newNode = new Node(e);  
        if(index == 0) {                        // 처음이라면  
            newNode.next = first;               // 새로운 노드는 첫 번째 노드를  
            first = newNode;                    // 추가한 노드가 첫 번째 노드가 되도록 함.  
        } else {  
            Node prev = getNode(index - 1); // 추가할 위치 직전 노드  
            newNode.next = prev.next;            // 추가할 노드는 직전 노드가 참조하는 다음 노드를 참조하도록 함.  
            prev.next = newNode;                 // 직전 노드가 추가한 노드를 참조하도록 함.  
        }  
        size++;  
    }  


    private Node getLastNode() {  
        Node x = first;  
        while(x.next != 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;  
    }  

    // 추가 코드  
    public Object remove(int index) {  
        Node removeNode = getNode(index);          // 삭제할 노드 위치 찾기  
        Object removedItem = 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 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;  
            }  
            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);  

        System.out.println("첫 번째 항목에 삭제");  
        list.remove(0); // remove First O(1)  
        System.out.println(list);  

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

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

    }  
}

// 실행 결과
MyLinkedListV1{first=[a -> b -> c], size=3}
첫 번째 항목에 추가
MyLinkedListV1{first=[d -> a -> b -> c], size=4}
첫 번째 항목에 삭제
MyLinkedListV1{first=[a -> b -> c], size=3}
중간 항목에 추가
MyLinkedListV1{first=[a -> e -> b -> c], size=4}
중간 항목에 삭제
MyLinkedListV1{first=[a -> b -> c], size=3}

정리

직접 만든 배열 리스트와 연결 리스트의 성능 비교 표

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한 칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 반면에 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분이 O(1)로 빠르다.
• 앞에 추가하는 경우
  • 연결 리스트는 배열 리스트처럼 추가한 항목의 오른쪽에 있는 데이터를 모두 한 칸씩 밀지 않아도 된다.
  • 일부 노드의 참조만 변경하면 된다.
  • 따라서 데이터를 앞쪽에 추가하는 경우 보통 연결 리스트가 더 좋은 성능을 제공한다.
  • 배열 리스트
    • 데이터를 앞쪽에 추가하는 경우 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. O(n)
  • 연결 리스트
    • 데이터를 앞쪽에 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)
• 마지막에 데이터를 추가하는 경우
  • 배열 리스트
    • 인덱스로 마지막 위치를 바로 찾을 수 있다. O(1)
    • 데이터를 마지막에 추가하는 경우 데이터를 이동하지 않아도 된다. O(1)
    • 따라서 O(1)의 성능을 제공한다.
  • 연결 리스트
    • 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다.
    • 따라서 마지막 노드를 찾는데 O(n)의 시간이 걸린다.
    • 데이터를 추가하는 경우 일부 노드의 참조만 변경하면 된다. O(1)
    • 따라서 O(n)의 성능을 제공한다.

배열 리스트 vs 연결 리스트 사용

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

참고 - 단일 연결 리스트, 이중 연결 리스트

지금까지 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트다.
노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다.

자바가 제공하는 연결 리스트는 이중 연결 리스트다.
추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 삭제하는 경우에도 O(1)의 성능을 제공한다.

이중 연결 리스트 예시다.

public class Node { 
    Object item; 
    Node next; //다음 노드 참조 
    Node prev; //이전 노드 참조 
}

마지막 노드를 참조하는 연결 리스트

public class LinkedList { 
    private Node first; 
    private Node last; //마지막 노드 참조 
    private int size = 0; 
}

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

지금까지 만든 연결 리스트에 제네릭을 도입해서 타입 안전성을 높여본다.
추가로 여기서 사용하는 Node 는 외부에서 사용되는 것이 아니라 연결 리스트 내부에서만 사용된다.
따라서 중첩 클래스로 만든다.

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<E> lastNode = getLastNode();  
            lastNode.next = newNode;  
        }  
        size++;  
    }  

    public void add(int index, E e) {  
        Node<E> newNode = new Node<>(e);  
        if(index == 0) {  
            newNode.next = first;  
            first = newNode;  
        } else {  
            Node<E> prev = getNode(index - 1);  
            newNode.next = prev.next;  
            prev.next = newNode;  
        }  
        size++;  
    }  


    private Node<E> getLastNode() {  
        Node<E> x = first;  
        while(x.next != null) {  
            x = x.next;  
        }  
        return x;  
    }  

    public E 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 removedItem = removeNode.item;  
        if(index == 0) {  
            first = removeNode.next;  
        } 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 e) {  
        int index = 0;  
        for (Node<E> x = first; x != null; x = x.next) {  
            if(e.equals(x.item)) {  
                return index;  
            }  
            index++;  
        }  
        return -1;  
    }  

    public int size() {  
        return size;  
    }  

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

    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> 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();  
        }  
    }  
}

사용 예시

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

        MyLinkedListV3<Integer> integerList = new MyLinkedListV3<>();  
        integerList.add(1);  
        integerList.add(2);  
        integerList.add(3);  
        Integer integer = integerList.get(0);  
        System.out.println("integer = " + integer);  
    }  
}

// 결과
string = a
integer = 1

3. 요약

연결 리스트 자료 구조에 대해 구현하면서 알아보았다.
연결 리스트의 각 노드는 다음 노드를 참조한다.

데이터의 추가 및 삭제에 대한 빅오 표기법에 의한 성능까지 알아보았다.

영한이 형이 알려주고, 구현하는 연결 리스트 덕에 연결 리스트의 동작 원리와 특징에 대해 손쉽고 자세히 알아보았다...

다음은 List 에 대해 알아본다.

p.s 하고 싶은 말

ArrayList를 학습할 때부터지만, 일시 정지를 하고, 먼저 구현해보고 강의를 재생했는데,
예전에는 자료 구조하면 지레 겁부터 먹었다.
그나마 산전수전 쪼금 겪고(물론 내가 말하는 산전수전의 표현에 대한 깊이는 겁나게 얇다..) 강의를 보니 컬렉션이나 자료구조가 그리 어렵진 않은 거 같다...
(물론 어렵긴한데 할만하다.)

그림으로 설명해주시는 부분은 정말 이해가 잘 된다.

결론은 해당 강의를 통해 자료 구조를 탄탄하게 다진 다음 알고리즘을 섭렵해보고 싶다....!!