[JAVA]Collection(컬렉션)의 자료구조 정리 _Part02.LinkedList

Collection(컬렉션)의 자료구조 정리

 

이번엔 List의 LinkedList를 설명하려고 합니다.

해당 자료는 도식화해 해당 자료구조가 어떤 구조로 이루어졌는지 정리한 내용입니다.

 

Array(배열)는 생성시 사이즈를 지정해야하기때문에 확장성면에서 불편했고

ArrayList는 데이터를 확장측면에선 편하지만 데이터 추가, 삭제면에서 자유롭지 못했습니다.

(ArrayLIst 설명은...https://hwang890.tistory.com/entry/JAVACollection%EC%BB%AC%EB%A0%89%EC%85%98%EC%9D%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC-Part01ArrayList)

 

 

예전에 책에서 읽은 적이 있습니다.

개발자는 굉장히 게으른 사람들이라고.... 

그래서 최대한 편한? 합리적이고 효율적인 로직을 생각하는 것같습니다. (최소액션으로 최대효율)

 

ArrayList보다 더 진보한자료구조가 LinkedList입니다. 

진보했다고 했다고 해서 ArrayList보 무조건 좋다고 생각하면 안됩니다.

ArrayList보다 LinkedList의 이점이 있고 LinkedList보다 ArrayList의 이점이 있습니다.

 

ArrayList는 데이터를 읽는 속도가 index로 하기 때문에 매우빠르고 추가삭제면에서는 느린편입니다.
(단 순차적 추가삭제면에서는 끝에서 추가/삭제가 이뤄진다면 이점은 빠릅니다.) 

 

LinkedList는 데이터를 읽는 속도가 느리고 , 추가/삭제면에서 ArrayList보다 빠릅니다.
(단 위 설명처럼 순차적인 추가/삭제는 ArrayList가 빠르다.)

LinkedList

 

위 그림과 같이 데이터를 만들고 list라는 접근시 Stack의 주소를 읽어와 heap저장된 실제 물리주소를 알려줍니다.
(C의 Pointer개념이 이해하면 도움이됩니다.)

 

그러면 위 이미지처럼 LinkedList는 구조로 이뤄졌습니다. 

 

package _09_Collection.List;

import java.util.Comparator;
import java.util.LinkedList;

public class test {
	public static void main(String[] args) {
		
		LinkedList<Integer> list = new LinkedList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(5);
		list.add(6);
		list.add(7);
		list.add(8);
		list.add(9);
		list.add(10);
		System.out.println(list);   //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
		
		//리스트의 첫번쨰 데이터를 출력한다.
		int num = list.element();  
		System.out.println(num);  //1
		
		//요소 값을 검색시 해당 요소값의 인덱스를 출력한다.
		System.out.println(list.indexOf(3));   //2
		
		//리스트 내에 해당 요소값이 존재유무를 확인한다.
		System.out.println(list.contains(11));   //false
		System.out.println(list.contains(10));  //true
		
		//list의 지정한 인덱스에 요소값을 삽입한다. 
		list.add(3, 40);  
		System.out.println(list);  // [1, 2, 3, 40, 4, 5, 6, 7, 8, 9, 10]
		
		//데이터가 들어간 갯수를 카운트해준다. 
		System.out.println(list.size());   //11
		
		 //리스트가 비어있는 유무를 확인하며 true: 요소가 없다. false: 요소가 있다.
		System.out.println(list.isEmpty()); //false
		
		//리스트 안 요소를 모두 삭제한다.
		list.clear();
		
		//데이터가 들어간 갯수를 카운트해준다. 
		System.out.println(list.size()); 
		
		//리스트가 비어있는 유무를 확인하며 true: 요소가 없다. false: 요소가 있다.
		System.out.println(list.isEmpty()); //true

	}

}

밑에는 LinkedList에서 데이터 추가 시 발생하는 일을 도식화한것입니다.

LinkedList 데이터 추가 

 

위 데이터를 삭제시 반대로 NextAddress의 주소는 그전 데이터 주소를 해제하고 삭제된 그다음 주소를 바로 보게 될겁니다.

 

위 LinkedList는 단방향 검색이며 

 

어떤 데이터는 ex) 1, 2, 3, ...9, 10이라고는 LinkedList구조시 9번을 찾아야하는데

 

1번부터 순차 검색시 효율성이 떨어집니다.

 

그렇다면 10, 9, 8....2, 1이렇게 검색한다면 효율적일겁니다.

이것을 Double LinkedList라고하며 해당 DoubleLinkedList는 클래스가 따로 존재하지 않으며 개발자가 구현해야합니다.

 

Double LinkedList

위 이미지를 보면 맨 앞과 맨 뒤에는 데이터 가 없으니 주소는 null로 표기합니다. 

 

여기서 한번더 발전한게 Double Circular LinkedList이고 

데이터 구조가  Circular :  원형 입니다.

Double Circular LinkedList이름과 구조를 보면 데이터가 한 원형으로 존재합니다.

서로 단절된 포인트가 없습니다. 모두 연결된 구조입니다.