[Java] List (ArrayList, LinkedList)

1. ArrayList

기존의 존재하던 Vector 클래스를 개선한 클래스로 Vector의 구현원리, 기능적 측면에서 동일하다.
이름에서 알 수 있듯 List 인터페이스를 구현한 클래스로 중복을 허용하고 저장순서도 유지된다.

- Object 배열을 이용해서 데이터를 순차적으로 저장한다.
- 배열을 이용하였기 때문에 순차적인 데이터 입력 & 데이터를 읽는 속도가 빠르지만 크기를 변경할 수 없다. 또한 비순차적인 데이터의 추가 혹은 삭제는 속도가 느리다.

 

📢 ArrayList는 데이터를 읽고 저장하는데 효율이 좋지만, 용량을 변경해야하는 경우 새로운 배열을 생성 후 기존 배열을 복사해야하기 때문에 효율이 매우 떨어진다. 최초 ArrayList 생성 시 저장될 데이터의 개수를 고려해서 충분한 용량의 인스턴스를 생성해야 한다.

📌 ArrayList 메서드

메서드	반환타입	설 명
ArrayList()	생성자	크기가 10인 ArrayList 생성
ArrayList(Collection c)	생성자	ArrayList 생성 후 컬랙션 저장
ArrayList(int Capacity)	생성자	주어진 크기만큼의 인덱스를 가지는 ArrayList 생성
add(Object o)	boolean	ArrayList에 객체 저장
add(int index, Object e)	void	지정된 인덱스에 객체 저장
get(int index)	Object	지정된 위치에 저장된 객체 반환
indexOf(Object o)	int	주어진 객체가 저장된 위치를 반환
remove(int index)	Object	지정된 위치에 있는 객체 삭제 후 반환
remove(Object o)	boolean	지정한 객체를 삭제
set(int index, Object e)	Object	주어진 객체를 지정한 위치에 저장 (덮어쓰기)
int size()	int	저장된 객체 수 반환
subList(int from, int end)	List	from~end 사이의 객체  List로 반환
trimToSize()	void	capacity를 size만큼 줄임

package ch11;

import java.util.ArrayList;
import java.util.Collections;

public class Ex11_1 {

	public static void main(String[] args) {
		
		ArrayList list1 = new ArrayList(10);
		
//		list1.add(5);
		list1.add(new Integer(5));
		list1.add(4); // Wrap Class "Auto Boxing"으로 자동 변환
		list1.add(2);
		list1.add(0);
		list1.add(1);
		list1.add(3);
		
		ArrayList list2 = new ArrayList(list1.subList(1, 4));
		
		print(list1, list2);
		
		Collections.sort(list1); //Collection 인터페이스
		Collections.sort(list2); //Collections 클래스 구분할 것
		
		//containsAll(Object obj)
		//지정된 객체(obj)가 ArrayList에 포함되어있는지 확인 후 boolean 반환
		System.out.println("list1.containsAll(list2) : "+ list1.containsAll(list2));
		
		list2.add("B"); // 4, 2, 0, B
		list2.add("C"); // 4, 2, 0, B, C
		list2.add(3, "A"); // 4, 2, 0, A, B, C -> 3번째 인덱스에 있는 값 뒤로 밀어내고 입력
		
		print(list1, list2);
		
		list2.set(3, "AA"); // 4, 2, 0, AA, B, C
		print(list1, list2);
		
		//retainAll(Object o) : o와 겹치는 부분만 남기도 전부 삭제
		System.out.println("list1.retainAll(list2) : " + list1.retainAll(list2));
		
		print(list1, list2);
		
		//list2에서 list1 에 포함된 객체들을 삭제
		
		for(int i = list2.size()-1; i >= 0; i--) {
			if(list1.contains(list2.get(i))) {
				list2.remove(i);
			}
		}
		
		print(list1, list2);
	}
	
	static void print(ArrayList list1, ArrayList list2) {
		System.out.println("list1: " + list1);
		System.out.println("list2: " + list2);
	}
}

2. LinkedList

크기 변경이 불가능하고 비순차적인 데이터 입력/삭제가 느린 ArrayList의 단점을 보완하기 위한 LinkedList는
불연속적으로 존재하는 데이터를 서로 연결한(Link)한 형태로 구성되었다.

LinkedList에는 node라는 내포클래스가 존재하며 node에는 데이터와 함께 다음 데이터의 주소값이 저장된다.

ArrayList와 달리 비순차적인 데이터의 입력/삭제 시 node의 주소값만 변경하면 되므로 처리속도가 빠르다.

📌 LinkedList 종류

- LinkedList (단방향이기에 이전 데이터에 대한 접근이 불가하다.

- DoulbeLinkedList ( Node에 이전 데이터의 주소값을 추가하여 이전 데이터에 대한 접근이 가능하도록 함)
실제 LinkedList는 이름과 달리 DoubleLinkedList로 구현되어 있다.

- DoubleCircularLinkedList (리스트의 마지막 데이터와 첫 번째 데이터를 연결)

📌 LinkedList 메서드

LinkedList 또한 ArrayList와 마찬가지로 List 인터페이스를 구현하였기에 ArrayList와 크게 다른게 없다.

메서드	반환타입	설 명
LinkedList()	생성자	크기가 10인 LinkedList 생성
LinkedList(Collection c)	생성자	LinkedList 생성 후 컬랙션 저장
add(Object o)	boolean	ArrayList에 객체 저장
add(int index, Object e)	void	지정된 인덱스에 객체 저장
get(int index)	Object	지정된 위치에 저장된 객체 반환
indexOf(Object o)	int	주어진 객체가 저장된 위치를 반환
remove(int index)	Object	지정된 위치에 있는 객체 삭제 후 반환
remove(Object o)	boolean	지정한 객체를 삭제
set(int index, Object e)	Object	주어진 객체를 지정한 위치에 저장 (덮어쓰기)
int size()	int	저장된 객체 수 반환
subList(int from, int end)	List	from~end 사이의 객체  List로 반환
trimToSize()	void	capacity를 size만큼 줄임

💬 ArrayList와 LinkedList의 비교

⊳ ArrayList는 순차적 추가/삭제할 경우 LinkedList보다 빠르지만 메모리 사용이 비효율적이다.

⊳ LinkedList는 비순차적 추가/삭제할 경우 ArrayList보다 빠르지만 데이터가 많을수록 접근성이 떨어진다.