JAVA - LinkedList(링크드리스트)

도서 - 자바의 정석을 보며 공부한 내용

링크드 리스트라는 자료구조가 고안된 이유

• 배열 장점
  • 가장 기본적인 형태의 자료구조, 구조가 간단하며 사용하기 쉬움, 데이터를 읽어 오는데 걸리는 시간이 가장 빠르다.
• 배열 단점
  • 크기 변경 불가능(새로운 배열을 생성해 데이터 복사 ⇒메모리낭비)
  • 비순차적인 데이터의 추가 삭제에 시간이 오래걸림(배열의 중간에 데이터를 추가하 려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야함.

LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성됨

class Node {
		Node next; // 다음 요소의 주소를 저장
		Object obj; // 데이터를 저장
}	

1. LinkedList에서의 데이터 삭제 → 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음요소를 참조하도록 변경하면됨. 즉 단 하나의 참조만 변경하면 삭제가 이루어짐.
2. 새로운 데이터를 추가할 때 → 새로운 요소 생성후 추가하려는 위치의 이전 요소의 참조를 새로운 요소로 변경 후 새로운 요소가 그 다음 요소를 참조하도록 변경하면됨

즉, 처리속도가 매우 빠름

더블 링크드 리스트(이중 연결리스트, doublylinked list)

• 링크드 리스트는 이동방향이 단방향 → 이전 요소에 대한 접근은 어려움
• 더블 링크드 리스트 → 링크드 리스트에 참조변수를 하나 더 추가하여 이전 요소에 대한 참조도 가능하도록 한게 끝
• 링크드 리스트보다 더 많이 사용됨.

class Node {
		Node next; // 다음 요소의 주소를 저장
		Node previous;// 이전 요소의 주소를 저장
		Object obj;    // 데이터를 저장
}

💡 실제로 LinkedList 클래스는 이름과 달리 링크드 리스트가 아닌 더블 링크드 리스트로 구현되어 있음 →LinkedList의 낮은 접근성을 높이기 위함

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

• 배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산으로 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있다.
• LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다(접근시간이 길어진다는 단점)

총 정리

ArrayList

• 접근시간 - 빠름
• 추가/삭제 - 느림
• 비효율적인 메모리 사용

LinkedList

• 접근시간 - 빠름
• 추가삭제 느림
• 데이터가 많을수록 접근성이 떨어짐

두 클래스의 장점을 이용해 두 클래스를 조합해서 사용하는방법

ArrayList al = new ArrayList(1000000);
for(int i = 0; i < 100000; i++) {
		al.add(i+"");
}
LinkedList ll = new LinkedList(al);
for(int i = 0; i < 1000; i++) {
		ll.add(500, "X");
}

컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스들은 서로 변환이 가능한 생성자를 제공함