[Java] List 인터페이스와 클래스 - 총정리

 

 [ Collection 구조 정리글 : https://bangu4.tistory.com/194 ]

[Java] Java Collection 구조 정리

 

Collection 자료구조중 List 에 대해서 정리해보겠다.

 

LIST 인터페이스

index 라는 식별자로 순서를 가지며, 데이터의 중복을 허용하는 자료구조이다.

1. List 자료구조의 특징 

- 중복 : 중복 가능 , index가 순차적 Key로 유일성을 가짐
- 순서 : 순서 보장 
- 정렬 : 정렬 가능 , Collections.sort()를 통해 제공됨
- 동기화 (Thread-Safe) : 동기화 불가능, 불안전함

• ArrayList
  • 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회(검색)이 빠름
  • 데이터삽입 / 삭제시 느림

 

• LinkedList
  • 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정 하면 되기에 유용
  • 데이터 삽입 / 삭제시 빠름
  • 데이터 검색성능이 나쁘다.  처음부터 순차적으로 노드를 순화해야 되기 때문에 느림

 

• Vector
  - 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지 않음
  - 현재도 사용은 가능하나 호환성을 위해서만 남아있으니, 사용하지 않는걸 권장함

 

 

 

 

 

2. 주요 메소드

 

LIST 인터페이스 메소드

boolean add(E e)	해당 리스트(list)에 전달된 요소를 추가함. (선택적 기능)
void add(int index, E e)	해당 리스트의 특정 위치에 전달된 요소를 추가함. (선택적 기능)
void clear()	해당 리스트의 모든 요소를 제거함. (선택적 기능)
boolean contains(Object o)	해당 리스트가 전달된 객체를 포함하고 있는지를 확인함.
boolean equals(Object o)	해당 리스트와 전달된 객체가 같은지를 확인함.
E get(int index)	해당 리스트의 특정 위치에 존재하는 요소를 반환함.
boolean isEmpty()	해당 리스트가 비어있는지를 확인함.
Iterator<E> iterator()	해당 리스트의 반복자(iterator)를 반환함.
boolean remove(Object o)	해당 리스트에서 전달된 객체를 제거함. (선택적 기능)
boolean remove(int index)	해당 리스트의 특정 위치에 존재하는 요소를 제거함. (선택적 기능)
E set(int index, E e)	해당 리스트의 특정 위치에 존재하는 요소를 전달받은 객체로 대체함. (선택적 기능)
int size()	해당 리스트의 요소의 총 개수를 반환함.
Object[] toArray()	해당 리스트의 모든 요소를 Object 타입의 배열로 반환함.

http://tcpschool.com/java/java_collectionFramework_concept : 주요메소드 참조

 

1) ArrayList

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

public class ArrayListExam {
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<>();
		
		// add로 데이터 추가
		System.out.println("add로 데이터 초기화");
		for(int i=0;i<10;i++)
			list.add(i);
		
		// size()로 데이터 크기 반환
		System.out.println("리스트 size : "+list.size());

		
		// get()으로 데이터에 접근 출력
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
		
		// remomve()로 데이터 삭제
		System.out.println("\nremove(4) 수행");
		list.remove(4);

		
		
		// 이터레이터로 출력
		Iterator<Integer> it = list.iterator();
		while(it.hasNext())
			System.out.print(it.next()+" ");
		
		// desc sort
		System.out.println("\n내림차순 소팅 : ");
		Collections.reverse(list);
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
		
		System.out.println("\n오름차순 소팅 : ");

		// asc sort
		Collections.sort(list);
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
			
	}
}

 

2) LinkedList

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListExam {
	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<>();
		// add로 데이터 추가
		System.out.println("add로 데이터 초기화");
		for(int i=0;i<10;i++)
			list.add(i);
		
		// size()로 데이터 크기 반환
		System.out.println("리스트 size : "+list.size());

		
		// get()으로 데이터에 접근 출력
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
		
		// remomve()로 데이터 삭제
		System.out.println("\nremove(4) 수행");
		list.remove(4);

		
		
		// 이터레이터로 출력
		Iterator<Integer> it = list.iterator();
		while(it.hasNext())
			System.out.print(it.next()+" ");
		
		// desc sort
		System.out.println("\n내림차순 소팅 : ");
		Collections.reverse(list);
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
		
		System.out.println("\n오름차순 소팅 : ");

		// asc sort
		Collections.sort(list);
		for(int i=0;i<list.size();i++)
			System.out.print(list.get(i)+" ");
	}
}

3) Collections

리스트의 경우 Collections static Method를 자주활용하게 되므로 정리해 보았습니다.

		// List의 Class 중 ArrayList, Stack을 사용하여 코드작성
		ArrayList<Integer> list = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		//초기화
		for (int i = 0; i < 10; i++)
			list.add(i);
		for (int i = 0; i < 10; i++)
			s.push(i);
		
		// max() , min() 최대 최소 찾기
		System.out.println("s max() : " + Collections.max(s));
		System.out.println("list min() : " + Collections.min(list));
		
		//sort()
		Collections.sort(s); //오름차순
		Collections.reverse(s); //내림차순
		Collections.sort(s, Collections.reverseOrder()); // 내림차순 
		System.out.print("\n역순 출력 : ");
		for(int i : s)
			System.out.print(i+" ");
		System.out.println("\n");
		
		
		// 섞기(Shuffling) 랜덤하게 섞는다
		Collections.shuffle(s);
		System.out.print("랜덤 출력 : ");
		for(int i : s)
			System.out.print(i+" ");
		System.out.println("\n");

		// binarySearch() -> 해당값의 index를 반환 (실패시 -1 반환)
		// 오름차순 정렬이 되어있어야 사용가능하다.
		Collections.sort(s); //오름차순
		System.out.print("정방향 정렬 : ");
		for(int i : s)
			System.out.print(i+" ");
		System.out.println("\n\n이진탐색 5값의 위치: "+Collections.binarySearch(s, 5));
		
		// 두 리스트가 다른지 확인 disjoint
		// 두 리스트중 공통값이 있으면 False
		ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(99,88));
		System.out.println("\ndisjoint (완전히 다른가?) : "+ Collections.disjoint(list, list2));
		
		
	}

 

 

 

 

3. 시간복잡도

ArrayList 시간복잡도

add             : O(1)
remove          : O(n)
get             : O(1)
Contains        : O(n)
iterator.remove : O(n)
java 1.2에 추가, thread-safe 보장 안함

 특징 :  데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사
   - 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴
   - 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름

 

LinkedList 시간복잡도

add             : O(1)
remove          : O(1)
get             : O(n)
Contains        : O(n)
iterator.remove : O(1)
java 1.2에 추가, thread-safe 보장 안함

특징 : 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.
   - 데이터 추가/삭제시 빠름
   - 데이터 검색시 처음부터 노드를 순화해야 되기 때문에 느림