찰떡개발자 코딩

너무 기본적인 것들에 대해 정리가 되어있지 않아 초심으로 돌아가보려고 한다.

왜 사용하는지 다시한번 머리 속에 담아두자..!

배열 : 연속된 메모리의 집합

1). List

정의 : 데이터를 순차적으로 나열해 놓은 집합체.

장점 : 동적으로 사이즈가 자유롭게 변할 수 있다.

단점 :

• 배열과 비교했을때 
  • 배열 : 직접 엑세스로 (값을 넣거나 가져올때) 빠르다. -> 배열의 값으로 바로 접근가능하다.
  • List : 배열과 비교했을때 순차적 엑세스로 (값을 넣거나 가져올때) 조금 느리다. -> 메모리의 0번째 객체 주소부터 1,2,3... 로 읽어서 접근하는 방식이기 때문(순차적 엑세스)

종류 : 

• ArrayList :
  • 정의 : 크기를 동적으로 늘릴수있는 배열 객체 / 제네릭을 사용하여 타입을 지정해줄 수있다.
  • 장점 : 연속적으로 메모리 상에 존재하고, 시작배열 주소 + n*데이터 타입의크기를 통해서 바로 원하는 인덱스에 접근할 수 있어 검색 시 매우 빠르다.
  • 단점 : 값을 추가 하거나 삭제할때는 특정 값을 지우고 특정 값의 다음 값들을 전부 앞으로 땡기거나 뒤로 미는 방식임으로 느리다.
• LinedList : 
  • 정의 : 노드 간에 연결을 통해 리스트로 구현된 객체 => 메모리에서 연결되어있지 않고 
  • 장점 : 다음노드의 메모리 주소를 알고 있기 때문에 추가 삭제시 해당 연결정보만 변경해주면 됨으로 , 삭제시 매우 빠르다. => 삭제, 추가시 다음 노드의 주소값만 변경되면 됨
  • 단점 :
    • 인덱스를 가지고 있지 않기 때문에 탐색시 장점인 본인 주소와 다음값의 주소를 통해 값 하나하나를 개별적으로 찾아가기 때문에 속도가 느리다. 
    • ArrayList보다 더 많은 메모리를 소비한다. LinkedList의 요소들은 이전, 다음 요소들에 대한 정보를 가지고 있기 때문

시간 복잡도 비교

비교예제 :

public static void main(String[] args) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		long startTime = 0;
		long endTime = 0;
		long result = 0;

		// ArrayList add
		//시작 시간
		startTime = System.nanoTime();
		for (int i = 0; i < 100000; i++) {
		arrayList.add(i);
		}
		//끝시간
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("ArrayList add Time:  " + result);

		// LinkedList add
		startTime = System.nanoTime();
		for (int i = 0; i < 100000; i++) {
		linkedList.add(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("LinkedList add Time: " + result);

		// ArrayList get
		startTime = System.nanoTime();
		for (int i = 0; i < 10000; i++) {
		arrayList.get(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("ArrayList get Time:  " + result);
		// LinkedList get
		startTime = System.nanoTime();
		for (int i = 0; i < 10000; i++) {
		linkedList.get(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("LinkedList get Time: " + result);

		// ArrayList remove
		//전체 삭제 : 끝부터 시작점 까지
		startTime = System.nanoTime();
		for (int i = 9999; i >=0; i--) {
		arrayList.remove(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("ArrayList remove End to Start Time:  " + result);
		//전체 삭제 : 시작부터 끝 까지
		startTime = System.nanoTime();
		for (int i = 0; i<10000; i++) {
		arrayList.remove(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("ArrayList remove Start to End Time:  " + result);

		// LinkedList remove
		//전체 삭제 : 끝부터 시작점 까지
		startTime = System.nanoTime();
		for (int i = 9999; i >=0; i--) {
		linkedList.remove(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("LinkedList remove End to Start Time:  " + result);

		//전체 삭제 : 시작부터 끝 까지
		startTime = System.nanoTime();
		for (int i = 0; i<10000; i++) {
			linkedList.remove(i);
		}
		endTime = System.nanoTime();
		result = endTime - startTime;
		System.out.println("LinkedList remove Start to End Time:  " + result);

	}

결과 :

ArrayList add Time:  9679800
LinkedList add Time: 11414900
ArrayList get Time:  133800
LinkedList get Time: 90275600
ArrayList remove End to Start Time:  155203100
ArrayList remove Start to End Time:  160229000
LinkedList remove End to Start Time:  109419100
LinkedList remove Start to End Time:  141253900