본문 바로가기
[Naver Cloud Camp 7] 교육 정리

네이버 클라우드 캠프 38일차 230619

by 우기37 2023. 6. 20.

#1 교육정리

1) ArrayList

2) LinkedList

 

 

 

 

 

 

#2 ArrayList

목록 인터페이스의 크기 조정 가능한 배열 구현. 모든 선택적 목록 작업을 구현하고 null을 포함한 모든 요소를 허용합니다. 목록 인터페이스를 구현하는 것 외에도, 이 클래스는 목록을 저장하기 위해 내부적으로 사용되는 배열의 크기를 조작하는 방법을 제공합니다. (이 클래스는 동기화되지 않는다는 점을 제외하고는 벡터와 거의 동일합니다.)

 

또한, ArrayList은 자바의 JCF(Java Collections Framework) 자바 컬렉션 프래임워크 중 일부로 List 인터페이스를 상속받은 클래스 중 하나입니다.

 

크기, isEmpty, get, set, iterator 및 listIterator 작업은 일정한 시간에 실행됩니다. 추가 작업은 상각된 상수 시간으로 실행됩니다. 즉, n 요소를 추가하려면 O(n) 시간이 필요합니다. 다른 모든 작업은 선형 시간(대략적으로 말하자면)으로 실행된다. 상수 계수는 LinkedList 구현에 비해 낮습니다.

 

각 ArrayList 인스턴스에는 용량이 있습니다. 용량은 목록에 요소를 저장하는 데 사용되는 배열의 크기입니다. 그것은 항상 적어도 목록 크기만큼 큽니다. 요소가 ArrayList에 추가됨에 따라, 용량은 자동으로 증가합니다. 성장 정책의 세부 사항은 요소를 추가하는 것이 일정한 상각된 시간 비용을 초래한다는 사실 외에는 명시되지 않았습니다.

 

ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트입니다. 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점등이 유사하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고 있습니다.

 

이미지 출처 : https://coding-factory.tistory.com/551

 

아래는 코드와 함께 주석으로 설명을 정리해두었습니다.

공부하실 때 참고하시면 좋을 것 같습니다.

 

 

java.util.ArrayList 사용법)

// java.util.ArrayList 사용법
package com.eomcs.basic.ex03;

import java.util.ArrayList;
import java.util.Date;

public class Exam0110 {

  public static void main(String[] args) {

    // 자바 컬렉션 API (collection API)
    // => 자바에서 데이터 목록을 다루는 클래스를 말한다.
    // => java.util.Collection 인터페이스를 구현한 객체이다.
    //
    // ArrayList
    // - 배열을 이용하여 객체 목록을 다룬다.
    // - 단점:
    //   - 배열의 크기가 고정되기 때문에 배열을 초과하여 값을 넣으려면
    //     더 큰 새 배열을 만들고, 기존 값을 복사해야 한다.
    //   - 배열의 크기가 늘 때마다 가비지(garbage)가 생기는 문제가 있다.
    //   - 새배열에 기존 배열의 값을 복사하기 때문에 속도가 느린 문제도 있다.
    //
    //
    ArrayList list = new ArrayList();
    list.add("Hello");
    list.add(Integer.valueOf(100));
    list.add(100); // auto-boxing => list.add(Integer.valueOf(100)) 
    list.add(new Date());

    // ArrayList는 제네릭이 적용되어 있기 때문에
    // 저장할 객체의 타입을 명확히 지정하라.
    // 모든 종류의 인스턴스를 저장하고 싶다면,
    // 다음과 같이 타입 파라미터에 Object 타입을 전달하라.
    ArrayList<Object> list2 = new ArrayList<>();
    list2.add("Hello");
    list2.add(Integer.valueOf(100));
    list2.add(100);
    list2.add(new Date());
  }
}

 

 

java.util.ArrayList 사용법 - 추가, 변경, 삭제)

ArrayList에 값을 추가하려면 ArrayList의 add(index, value) 메소드를 사용하면 됩니다. index를 생략하면 ArrayList 맨 뒤에 데이터가 추가되며 index중간에 값을 추가하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 뒤로 밀려납니다. 

 

ArrayList에 값을 제거하려면 ArrayList의 remove(index) 메소드를 사용하면 됩니다. remove()함수를 사용하여 특정 인덱스의 객체를 제거하면 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨집니다. 모든 값을 제거하려면 clear() 메소드를 사용하면 됩니다.

 

 

// java.util.ArrayList 사용법 - 추가, 변경, 삭제
package com.eomcs.basic.ex03;

import java.util.ArrayList;

public class Exam0120 {
  public static void main(String[] args) {
    // 특정 타입의 목록을 다루고 싶다면,
    // 타입 파라미터로 해당 타입을 지정하라.
    //
    ArrayList<String> list = new ArrayList<>();
    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    list.add("ddd");
    System.out.println(list); // [aaa, bbb, ccc, ddd]

    // ArrayList는 null을 추가하는 것을 허용한다.
    list.add(null);
    list.add("eee");
    System.out.println(list); // [aaa, bbb, ccc, ddd, null, eee]

    // ArrayList는 같은 인스턴스를 중복해서 추가할 수 있다.
    list.add(null);
    list.add("aaa");
    list.add("bbb");
    System.out.println(list); // [aaa, bbb, ccc, ddd, null, eee, null, aaa, bbb]

    // remove(index)
    // - 목록에서 해당 인덱스의 값을 삭제한다.
    // - 리턴 값은 삭제된 값이다.
    String s = list.remove(2);
    System.out.println(s); // ccc
    System.out.println(list); // [aaa, bbb, ddd, null, eee, null, aaa, bbb]

    list.remove(0);
    System.out.println(list); // [bbb, ddd, null, eee, null, aaa, bbb]

    // add(index, value)
    // - 해당 위치에 값을 삽입한다.
    list.add(1, "xxx");
    System.out.println(list); // [bbb, xxx, ddd, null, eee, null, aaa, bbb]

    list.add(1, "yyy");
    System.out.println(list); // [bbb, yyy, xxx, ddd, null, eee, null, aaa, bbb]

    list.add(0, "zzz");
    System.out.println(list); // [zzz, bbb, yyy, xxx, ddd, null, eee, null, aaa, bbb]

    list.add(5, "ttt");
    System.out.println(list); // [zzz, bbb, yyy, xxx, ddd, ttt, null, eee, null, aaa, bbb]

    // set(index, value)
    // - 해당 위치의 값을 변경한다.
    list.set(1, "aaa");
    System.out.println(list); // [zzz, aaa, yyy, xxx, ddd, ttt, null, eee, null, aaa, bbb]

    // get(index) : 해당 위치의 값을 리턴한다.
    System.out.println(list.get(2)); // yyy
    System.out.println(list.get(3)); // xxx

    // 인덱스가 유효하지 않을 때 IndexOutOfBoundsException 예외가 발생한다.
    //    System.out.println(list.get(100));
  }
}

 

 

java.util.ArrayList 사용법 - contains() 와 equals()의 관계)

ArrayList에서 찾고자 하는 값을 검색하려면 ArrayList의 contains(value) 메소드를 사용하면 됩니다. 만약 값이 있다면 true가 리턴되고 값이 없다면 false가 리턴됩니다. 값을 있는 index를 찾으려면 indexOf(value) 메소드를 사용하면 되고 만약 값이 없다면 -1을 리턴합니다.

 

// java.util.ArrayList 사용법 - contains() 와 equals()의 관계
package com.eomcs.basic.ex03;

import java.util.ArrayList;

public class Exam0130 {
  public static void main(String[] args) {

    class Member {
      String name;
      int age;

      public Member(String name, int age) {
        this.name = name;
        this.age = age;
      }

      @Override
      public String toString() {
        return "Member [name=" + name + ", age=" + age + "]";
      }

      //      @Override
      //      public int hashCode() {
      //        final int mrime = 31;
      //        int result = 1;
      //        result = mrime * result + age;
      //        result = mrime * result + ((name == null) ? 0 : name.hashCode());
      //        return result;
      //      }

      @Override
      public boolean equals(Object obj) {
        if (this == obj)
          return true;
        if (obj == null)
          return false;
        if (getClass() != obj.getClass())
          return false;
        Member other = (Member) obj;
        if (age != other.age)
          return false;
        if (name == null) {
          if (other.name != null)
            return false;
        } else if (!name.equals(other.name))
          return false;
        return true;
      }
    }

    Member m1 = new Member("홍길동", 20);
    Member m2 = new Member("임꺽정", 30);
    Member m3 = new Member("유관순", 17);

    ArrayList<Member> list = new ArrayList<>();
    list.add(m1);
    list.add(m2);
    list.add(m3);
    System.out.println(list);

    // contains()
    // - 해당 인스턴스와 같은 객체가 있는지 알아낸다.
    // - 단 인스턴스 주소를 비교하는 것이 아니라
    //   equals()의 결과가 true 인지 비교한다.
    // - hashCode()의 리턴 값이 같을 필요는 없다.
    //
    Member m4 = new Member("임꺽정", 30);
    System.out.println(list.contains(m4)); // true

    System.out.println(m2 == m4);
    System.out.println(m2.equals(m4));
    System.out.println(m2.hashCode() == m4.hashCode());

  }
}


[Member [name=홍길동, age=20], Member [name=임꺽정, age=30], Member [name=유관순, age=17]]
true
false
true
false

 

 

java.util.ArrayList 사용법 - indexOf() )

// java.util.ArrayList 사용법 - indexOf()
package com.eomcs.basic.ex03;

import java.util.ArrayList;

public class Exam0140 {
  public static void main(String[] args) {

    class Member {
      String name;
      int age;

      public Member(String name, int age) {
        this.name = name;
        this.age = age;
      }

      @Override
      public String toString() {
        return "Member [name=" + name + ", age=" + age + "]";
      }

      //      @Override
      //      mublic int hashCode() {
      //        final int mrime = 31;
      //        int result = 1;
      //        result = mrime * result + age;
      //        result = mrime * result + ((name == null) ? 0 : name.hashCode());
      //        return result;
      //      }

      @Override
      public boolean equals(Object obj) {
        if (this == obj)
          return true;
        if (obj == null)
          return false;
        if (getClass() != obj.getClass())
          return false;
        Member other = (Member) obj;
        if (age != other.age)
          return false;
        if (name == null) {
          if (other.name != null)
            return false;
        } else if (!name.equals(other.name))
          return false;
        return true;
      }
    }

    Member m1 = new Member("홍길동", 20);
    Member m2 = new Member("임꺽정", 30);
    Member m3 = new Member("유관순", 17);

    ArrayList<Member> list = new ArrayList<>();
    list.add(m1);
    list.add(m2);
    list.add(m3);
    System.out.println(list);

    // indexOf(값)
    // - 목록에 같은 값을 가진 객체의 인덱스를 알아낸다.
    // - 값을 비교할 때는 contains()와 마찬가지로
    //   equals()의 리턴 값이 true인 경우 같은 값으로 간주한다.
    //
    Member m4 = new Member("유관순", 17);
    System.out.println(list.indexOf(m4)); // 2

    System.out.println(m3 == m4);
    System.out.println(m3.equals(m4));
    System.out.println(m3.hashCode() == m4.hashCode());

  }
}


[Member [name=홍길동, age=20], Member [name=임꺽정, age=30], Member [name=유관순, age=17]]
2
false
true
false

 

 

목록 조회: 반복문과 인덱스를 이용한 목록 조회)

ArrayList의 get(index) 메소드를 사용하면 ArrayList의 원하는 index의 값이 리턴됩니다. 전체출력은 대부분 for문을 통해서 출력을하고 Iterator를 사용해서 출력을 할수도 있습니다.

 

// 목록 조회: 반복문과 인덱스를 이용한 목록 조회
package com.eomcs.basic.ex03;

import java.util.ArrayList;

public class Exam0210 {
  public static void main(String[] args) {

    class Member {
      String name;
      int age;

      public Member(String name, int age) {
        this.name = name;
        this.age = age;
      }

      @Override
      public String toString() {
        return "Member [name=" + name + ", age=" + age + "]";
      }

      //      @Override
      //      mublic int hashCode() {
      //        final int mrime = 31;
      //        int result = 1;
      //        result = mrime * result + age;
      //        result = mrime * result + ((name == null) ? 0 : name.hashCode());
      //        return result;
      //      }

      @Override
      public boolean equals(Object obj) {
        if (this == obj)
          return true;
        if (obj == null)
          return false;
        if (getClass() != obj.getClass())
          return false;
        Member other = (Member) obj;
        if (age != other.age)
          return false;
        if (name == null) {
          if (other.name != null)
            return false;
        } else if (!name.equals(other.name))
          return false;
        return true;
      }
    }

    Member m1 = new Member("홍길동", 20);
    Member m2 = new Member("임꺽정", 30);
    Member m3 = new Member("유관순", 17);

    ArrayList<Member> list = new ArrayList<>();
    list.add(m1);
    list.add(m2);
    list.add(m3);

    for (int i = 0; i < list.size(); i++) {
      Member m = list.get(i);
      System.out.printf("이름: %s, 나이: %d\n", m.name, m.age);
    }
  }
}


이름: 홍길동, 나이: 20
이름: 임꺽정, 나이: 30
이름: 유관순, 나이: 17

 

 

목록 조회: Iterator 사용)

Iterator는 컬렉션 객체를 순회하고 요소에 접근하기 위한 인터페이스입니다. Iterator를 사용하면 컬렉션의 내부 구조에 상관없이 일관된 방식으로 요소에 접근할 수 있습니다. Iterator를 사용하여 컬렉션의 요소를 반복적으로 처리할 수 있습니다.

// 목록 조회: Iterator 사용
package com.eomcs.basic.ex03;

import java.util.ArrayList;
import java.util.Iterator;

public class Exam0230 {
  public static void main(String[] args) {

    class Member {
      String name;
      int age;

      public Member(String name, int age) {
        this.name = name;
        this.age = age;
      }

      @Override
      public String toString() {
        return "Member [name=" + name + ", age=" + age + "]";
      }

      //      @Override
      //      mublic int hashCode() {
      //        final int mrime = 31;
      //        int result = 1;
      //        result = mrime * result + age;
      //        result = mrime * result + ((name == null) ? 0 : name.hashCode());
      //        return result;
      //      }

      @Override
      public boolean equals(Object obj) {
        if (this == obj)
          return true;
        if (obj == null)
          return false;
        if (getClass() != obj.getClass())
          return false;
        Member other = (Member) obj;
        if (age != other.age)
          return false;
        if (name == null) {
          if (other.name != null)
            return false;
        } else if (!name.equals(other.name))
          return false;
        return true;
      }
    }

    Member m1 = new Member("홍길동", 20);
    Member m2 = new Member("임꺽정", 30);
    Member m3 = new Member("유관순", 17);

    ArrayList<Member> list = new ArrayList<>();
    list.add(m1);
    list.add(m2);
    list.add(m3);

    // ArrayList의 값을 꺼내주는 일을 할 객체를 얻는다.
    Iterator<Member> iterator = list.iterator();

    // Iterator(데이터 꺼내주는 일을 하는 객체)에게 데이터를 달라고 요청한다.
    while (iterator.hasNext()) {
      Member m = iterator.next();
      System.out.printf("이름: %s, 나이: %d\n", m.name, m.age);
    }
  }
}

이름: 홍길동, 나이: 20
이름: 임꺽정, 나이: 30
이름: 유관순, 나이: 17

 

 

목록 조회: 제네릭 적용)

// 목록 조회: 제네릭 적용
package com.eomcs.basic.ex03;

public class Exam0311 {

  static class MyList<E> {	// E는 제네릭 타입 매개변수로, MyList의 요소의 타입을 나타냅니다.
    Object[] list = new Object[5];
    int size;

    public void add(E value) {	// 리스트에 요소를 추가합니다. value를 배열 list에 저장하고 size를 증가시킵니다.
      list[size++] = value;
    }

    @SuppressWarnings("unchecked")
    public E get(int i) {	// 인덱스 i에 해당하는 요소를 반환합니다. 반환할 때는 캐스팅을 통해 제네릭 타입을 유추합니다.
      return (E) list[i];
    }

    public int size() {
      return size;
    }
  }

  static class Member {
    String name;
    int age;

    public Member(String name, int age) {
      this.name = name;
      this.age = age;
    }
  }

  public static void main(String[] args) {	// 제네릭을 사용하여 MyList에는 Member 타입의 객체만 저장할 수 있도록 제한합니다.

    Member m1 = new Member("홍길동", 20);
    Member m2 = new Member("임꺽정", 30);
    Member m3 = new Member("유관순", 17);

    MyList<Member> list = new MyList<>();
    list.add(m1);
    list.add(m2);
    list.add(m3);
    //list.add(new String("Hello!")); // 컴파일 오류!

    for (int i = 0; i < list.size(); i++) {
      Member m = list.get(i);
      System.out.printf("이름: %s, 나이: %d\n", m.name, m.age);
    }
  }
}


이름: 홍길동, 나이: 20
이름: 임꺽정, 나이: 30
이름: 유관순, 나이: 17

 

 

 

#3 LinkedList

연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다.

 

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다.

 

중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

 

그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋습니다.

 

 

LinkedList는 양방향 연결 리스트(Doubly Linked List)로 구현되어 있고 각각의 데이터가 노드로 구성되어 연결이 되는 구조입니다.

즉 각각의 노드는 다음 노드(next) 와 이전 노드(prev) 값을 내부적으로 가지고 있습니다.

추가나 삭제를 할 경우 변경되는 노드만 다시 연결해주면 됩니다. 그래서 주로 ArrayList는 검색이 많은 경우에 사용하고 LinkedList는 잦은 삽입/삭제 시 사용합니다.

 

이미지 출처 : https://coding-factory.tistory.com/552

 

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하는데 비해서 LinkedList는 위와 같이 인접 참조를 링크해서 체인처럼 관리합니다.

 

위 그림도 조금 이해하기 어렵다면 아래 그림도 참고해서 공부해보세요!

 

 

LinkedList 선언)

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

 

 

위 그림을 보면 LinkedList는 각기 노드마다 화살표로 연결되어 리스트 형태로 나열되어 있는 것을 볼 수 있다. 여기서 노드는 하나의 객체라고 보면된다. 즉, 객체를 만들면 객체의 주소가 생기게 되는데, 노드마다 각기 객체의 주소를 서로 참조함으로서 연결 형태를 구성하는 것이다.

단일 노드를 그림과 코드로 표현한다면 다음과 같이 될 것이다.

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};
 

LinkedList 종류)

 

단방향 연결 리스트 (singly linked list)

위에서 보았듯이, 다음 노드를 가리키기 위한 포인터 필드 next만을 가지고 있는 링크드 리스트를 singly linked list라고 한다. 하지만 단일 연결 리스트는 현재 요소에서 이전 요소로 접근해야 할때 매우 부적합한 특징이 있다.

예를들어 LinkedList에 저장된 데이터가 10000개라면 9999 번째 데이터에 접근하려면 Node를 9999번 이동해야 하기 때문이다. 이를 극복한 것이 doubly linked list 구조 이다.

 

양방향 연결 리스트 (doubly linked list)

 
class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    Node prev; // 이전 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
};
 

이중 연결이라서 대단한건 아니고, 기존의 단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드 prev가 추가된 형태를 doubly linked list라고 부른다.

singly linked list는 이동 방향이 단방향이기 때문에, 이를 보완하여 역순으로도 검색이 가능하도록 한 것이다. 따라서 doubly linked list는 singly linked list보다 각 요소에 대한 접근과 이동이 쉽기 때문에 기본적으로 많이 사용된다.

Tip

실제로 Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 doubly linked list로 구현 되어 있다.

 

양방향 원형 연결 리스트 (doubly circular linked list)

추가로 doubly linked list 보다 접근성이 더 개선된 doubly circular linked list도 있다. 이 역시 대단한건 아니고 단순히 첫번째 노드와 마지막 노드를 각각 연결시켜, 마치 원형 리스트 처럼 만들었다고 보면 된다.

이러한 구조는 티비 채널을 순회하거나 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다고 보면 된다.

 

글 및 이미지 참고 : https://inpa.tistory.com/entry/JAVA-☕-LinkedList-구조-사용법-완벽-정복하기

 

아래는 코드로 보겠습니다.

// LinkedList 사용법
package com.eomcs.basic.ex04;

import java.util.LinkedList;

public class Exam0110 {

  public static void main(String[] args) {
    String s1 = new String("aaa");
    String s2 = new String("bbb");
    String s3 = new String("ccc");
    String s4 = new String("ddd");
    String s5 = new String("eee");

    LinkedList list = new LinkedList();
    list.add(s1);
    list.add(s2);
    list.add(s3);

    System.out.println(list.get(0));
    System.out.println(list.get(1));
    System.out.println(list.get(2));

    System.out.println(list.size());

    System.out.println(list.remove(1)); 
    print(list);  // aaa, ccc,

    list.add(s4); // aaa, ccc, ddd
    list.add(1, s5); // aaa, eee, ccc, ddd
    print(list);

    list.add(0, s2); // bbb, aaa, eee, ccc, ddd
    print(list);

    list.add(5, "xxx"); // bbb, aaa, eee, ccc, ddd, xxx
    print(list);
  }

  static void print(LinkedList list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i) + ", ");
    }
    System.out.println();
  }
}

// ArrayList vs LinkedList
// 1) 메모리
// ArrayList
//    => 고정 크기를 갖는다.
//    => 크기를 초과하면 새로 배열을 만들어야 하기 때문에 메모리 낭비가 심하다.
//    => 기존 배열은 가비지가 되기 때문에 가비지가 과다 생산된다.
// LinkedList
//    => 값을 넣을 때마다 새 메모리가 추가되는 가변 크기를 가진다.
//    => ArrayList 보다 메모리 낭비가 적고 가비지를 덜 생산한다.
// 2) 속도
// ArrayList
//    => 배열의 특징 상 인덱스를 이용하여 특정 항목을 찾을 때 속도 빠르다.
//    => 삭제할 때 이전 항목을 당겨와야 하기 때문에 속도가 느리다.
//    => 삽입할 때 현재 항목을 다음 항목으로 이동해야 하기 때문에 속도가 느리다.
// LinkedList
//    => 인덱스를 이용하여 특정 항목을 찾을 때 리스트의 처음부터 찾아야 하기 때문에 속도가 느리다.
//    => 삭제할 때 이전 항목과 다음 항목을 바로 연결하면 되기 때문에 속도가 빠르다.
//    => 삽입할 때 현재항목과 다음 항목을 새 항목과 연결하면 되기 때문에 속도가 빠르다.


aaa
bbb
ccc
3
bbb
aaa, ccc, 
aaa, eee, ccc, ddd, 
bbb, aaa, eee, ccc, ddd, 
bbb, aaa, eee, ccc, ddd, xxx,

 

ArrayList vs LinkedList)

  ArrayList LinkedList
컬렉션 구성 배열을 이용 노드를 연결(Linked)
데이터 접근 시간 모든 데이터 상수 시간 접근 위치에 따라 이동시간 발생
삽입 / 삭제 시간 삽입/삭제 자체는 상수 시간
삽입/삭제 시 데이터 이동이 필요한 경우 추가시간 발생 삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리사이징 필요 공간이 부족할 경우 새로운 배열에 복사하는 추가 시간 발생 -
데이터 검색 최악의 경우 리스트에 있는 아이템 수 만큼 확인
CPU Cache 캐시 이점을 활용 -