ArrayList
📌ArrayList란?
- List Interface를 상속받은 클래스로, 크기가 가변적인 선형 리스트
- 배열과 유사점 : 순차리스트 , 인덱스로 내부 객체 관리
- 배열과 차이점 : 객체들이 추가되어 용량이 넘친다면 자동으로 부족한 용량만큼 capacity를 늘려줌
📌ArrayList 선언
ArrayList list = new ArrayList() ; //매번 캐스팅을 새로 해주어야 해서 추천하지 않음 ArrayList<T> list = new ArrayList<T>(); //이런식으로 Generic을 사용하는 것을 권장 ArrayList<T> list = new ArrayList<T>(10); //초기 용량(Capacity) 설정
- Generic을 사용하여 선언하는 것이 권장됨 왜냐면, ArrayList list = new ArrayList() 이런식으로 사용하면 매번 캐스팅을 새로 해주어야 하는데 , 이는 에러를 발생시킬 가능성이 있음.
📌 ArrayList 값 추가
list.add(3); //값 추가 list.add(null);//null값도 추가 가능 list.add(1,10);//index 1뒤에 10 삽입
- index를 생략하면 맨 뒤에 데이터가 추가됨.
- index중간에 삽입하면 해당 인덱스부터 마지막 인덱스까지 모두 한칸씩 뒤로 밀림 > O(N)이 소요되겠네
- 중간 index에 값을 추가할 일이 많다면 ArrayList보다는 LinkedList를 사용하는 것이 유리함.
📌ArrayList 값 삭제
list.remove(1) ;//index1제거 list.clear();//원소 전부 삭제
- remove(index)를 사용하면 됨. 하지만 특정 인덱스를 제거하게 되므로 바로 뒤 인덱스부터 마지막 인덱스까지 모두 앞으로 1씩 당겨짐.
📌ArrayList 값 출력
for(Integer i : list){ System.out.println(i); } Iterator iter = list.iterator(); while(iter.hasNext()){ //다음 값이 있는지 체크 System.out.println(iter.next()); //값 출력 }
- get(index) 를 사용하면 ArrayList의 원하는 index값을 리턴해줌.
📌ArrayList 값 검색
System.out.println(list.contains(1)); // list에 1이 있는지 검색 true or false System.out.println(list.indexOf(1)); // 1이 있는 index의 반환, 없으면 -1 return
LinkedList
📌 LinkedList란?
- 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조
- Node는 linkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경이 되고 나머지 링크는 변경되지 않는다.
- 탐색, 정렬을 자주 하는 경우에는 배열을 사용하고, 데이터의 추가/삭제가 많은 경우에는 연결리스트를 사용하는 것이 적합나다.
📌 LinkedList선언
LinkedList list = new LinkedList(); //타입 미설정 Object로 선언한다. LinkedList<Student> members = new LinkedList<Student>(); LinkedList<Integer> num = new LinkedList<Integer>(); LinkedList<Integer> num2 = new LinkedList<>(); //파라미터 생략 가능 LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값 추가 가능
- LinkedList는 초기의 크기를 미리 설정할 수 없다.
- LinkedList를 생성할 때 잘못된 타입으로 캐스팅되어 오류가 발생하는 것을 막기 위해 LinkedList 사용 타입을 명시해주는 것이 좋다.
- int같은 기본 자료형은 사용할 수 없고, int를 객체화 시킨 wrapper 클래스를 사용해야 한다.
📌 LinkedList값 추가
LinkedList<Integer> list = new LinkedList<Integer>(); list.addFirst(1);//가장 앞에 데이터 추가 list.addLast(2);//가장 뒤에 데이터 추가 list.add(3);//데이터 추가 list.add(1,10);//index 1에 데이터 10 추가
- 대중적으로는 add(index, value) 메소드를 사용한다.
- index를 생략하면 가장 맨 뒤에 데이터가 추가된다.
📌 LinkedList값 삭제
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5)); list.removeFirst(); list.removeLast(); list.remove(); //생략시 0번째 데이터 제거 list.remove(1); //index 1 제거 list.clear(); //모든 값 제거
ArrayList vs LinkedList
📌 성능 차이
- 순차적으로 추가하기
- ArrayList: 순차적 추가의 경우 배열 원소의 이동이 없기 때문에 쉽게 가능
- LinkedList : 순차적으로 추가하고자 하면 추가하고자 하는 곳을 계속 찾아야 한다. 하지만 내부적으로 양방향으로 연결되어 있기 때문에 ArrayList와 큰 차이가 나지는 않는다.
- 중간에 추가하기
- ArrayList: 중간에 추가하려면 빈 공간을 만들어야 하기 때문에 원소의 이동이 필요하고, 상당히 비효율적이다.
- LinkedList: 중간에 추가할 때는 추가하고자 하는 원소의 앞 or 노드로 가서 가리키고 있는 주소만 추가해주면 되기 때문에 시간이 많이 소요되지 않는다.
- 중간에서 삭제하기
- ArrayList: 중간에 추가와 마찬가지로 중간에 빈 공간이 생기고, 이 공간을 채우기 위해 원소들이 이동 되어야 하므로 시간이 오래 걸린다.
- LinkedList: 중간에서 삭제하는 것도 추가하는 것과 마찬가지의 과정이다.
- 순차적으로 삭제하기
- ArrayList: 순차적으로 마지막 원소를 삭제할 때는 원소들의 이동이 필요 없기 때문에 시간이 오래 걸리지 않는다.
- LinkedList: 내부적으로는 양방향으로 연결되어 있기 때문에 ArrayList와 큰 차이가 나지는 않는다.
결론
- 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
- 중간 데이터를 추가/삭제 하는 경우에는 LinkedList가 ArrayList보다 빠르다.
Uploaded by Notion2Tistory v1.1.0