[ch11-12~14] LinkedList

장점:

첫 번쨰 요소 1을 읽어오는 것 하고

마지막 요소를 읽어오는 것 하고

접근시간이 똑같다

단점(1)

한 번 생성하면 

크기 변경할 수 없음!

 

어떻게 해야할까?

1) 더 큰 배열을 생성

2) 기존의 내용 복사하고

3) 참조를 변경해야한다

 

그렇다고 처음부터 크기를

넉넉하게 해버리면

메모리 낭비

좋은 건 아님

단점(2)

비순차적:

배열 중간에 있는 데이터를 

삭제 또는 추가하는 것을 의미

뒤의 데이터들이

이동을 하기 때문에

시간이 많이 걸린다.

 

중간의 데이터 추가,삭제는

시간이 많이 걸리지만

처음 끝과 마지막 끝은 빠름

배열의 단점:

1) 크기변경불가

2) 추가삭제 시간 多

 

이 단점들을 보완해서 나온 것

∴ LinkedLIst

배열은 각 요소가 연속적

(다닥다닥 붙어있음)

LinkedList는

각 요소가

어디에 있는 지 

알 수 없음

(불연속적)

요소 각각을 연결해 놓은 것

요소 하나를 Node라고 한다

자신의 다음노드가

어떤건 지 찾아갈 수 있는

참조변수를 갖고있다

어떤 노드가 있으면

자신의 다음노드를 가리킴

다음노드와 data

배열과 달리

데이터가 하나하나

연결됨

데이터 삭제:

값 하나만 바꿔주면

삭제되고 그걸로 끝남

(간단)

데이터 추가:

새로운 객체 만들고

연결을 바꿔주면 끝

객체 하나 만들고

두 번의 참조변경만 하면 됨

 

배열이었으면

뭐하나 집어넣으면

다 옮겨야 함

LinkedList의 단점:

접근성 나쁨

 

배열은

각 요소가 연속적이라서

한 번에 갈 수 있는 반면

 

LinkedList는 불연속적

한 번에 가는건 힘듦

(접근성이 나쁨)

LinkedList의 접근성이

나쁜 걸 개선한 것

=> 더블리 링크드 리스트

(이중 연결 리스트)

 

doubly linked list

서로 근접한 두 요소를

앞 뒤로 연결할 수 있게

해놓은 것

 

LinkedList는

두 번째 요소에서

첫 번째 요소로 가는 것 안됨

자기 다음 요소밖에 모름

Linkedlist는 

next뿐이지만

 

doublyLinkedList는

참조 2개를 갖고있다

(next-다음요소,

previous-이전요소)

그래서 앞으로도 갔다

뒤로도 갈 수 있음

하지만 한 번에

2,3개 건너뛰기는 힘듦

앞뒤로 이동만 원활

 

doublyLinkedList를

더 개선한 것이

이중원형연결리스트

이중원형연결리스트:

맨 마지막 요소의

다음을 맨 처음 요소와

연결해놓고

맨 처음요소는

맨 마지막 요소와 연결함

 

java는 이중연결리스트

<ArrayList와

LinkedList 성능비교>

 

비순차적으로

데이터 추가/삭제의 의미

= 중간에 추가,삭제한다는 뜻

 

읽기:

ArrayList

 

추가/삭제:

LinkedList가 더 빠르지만

비순차적일 때의 얘기

 

비효율적인 메모리사용은

성능을 높이려고

배열을 크게 잡은 것을 의미

 

자료구조 기반

ArrayList - 배열기반 (연속적)

LinkedList - 연결기반 (불연속적)

 

자료구조:

어떤 식으로 자료를

저장해야하는 지

정리해 놓은 학문