LinkedList

배열의 장점

• 배열은 구조가 간단하고, 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

배열은 구조가 간단하고, 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

 arr[0]에서 arr[4]로 가는 데 걸리는 시간, 또는 arr[3]을 읽는데 걸리는 시간을 구하려면, 배열 요소의 주소를 알아야 한다.

특정 배열 요소의 주소는 배열 주소 + (배열 요소의 크기 x 인덱스)

배열의 단점

1. 크기를 변경할 수 없다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

1. (실행 중) 크기를 변경할 수 없다.

• 크기를 변경해야 하는 경우, 새로운 배열을 생성 후 데이터를 복사해야 함
• 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨

크기를 변경해야 하는 경우, 새로운 배열을 생성 후 데이터를 복사해야 함

• ① 더 큰 배열 생성
• ② 기존 내용 복사
• ③ 참조 변경 - StringBuffer의 생성자(복습 바로가기)

| 참고 | 배열의 저장 공간 부족해서 새로운 배열을 만들 때 어떻게 해야 하는지 누가 물어본다면, 코드로 작성할 순 없어도, 3단계로 얘기할 수 있어야 한다.

 

크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨

처음부터 저장하려는 객체의 개수를 예측해서, 그것보다 조금만 더 넉넉하게 ArrayList(int inital)로 배열 길이를 지정해주면 좋다.

 

2. 비순차적인(중간에) 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

• 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
• 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

 

데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.

'비순차적인 데이터의 추가 또는 삭제'라는 것은, 배열 중간에 있는 데이터를 삭제하거나 새로 추가하는 것을 말한다. 중간에 있는 데이터를 지우려면, 뒤에 있는 데이터를 옮겨야 하는데, 뒤에 있는 데이터 엄청 많으면, 그만큼의 데이터를 다 옮겨야 한다. 그래서 시간이 많이 걸린다.

 

그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

중간에 있는 데이터의 추가 및 삭제는 시간이 많이 걸리지만, 맨 끝에 있는 데이터의 삭제 또는 추가는 시간이 많이 걸리지 않는다. 즉, 순차적삭제는 바르다.

 

LinkedList - 배열의 단점을 보완

• 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)
• 데이터의 삭제 : 단 한번의 참조변경만 가능
• 데이터의 추가 : 한번의 Node객체 생성과 두 번의 참조변경만 가능

배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)

데이터의 삭제 : 단 한번의 참조변경만 가능

 

데이터의 추가 : 한번의 Node객체 생성과 두 번의 참조변경만 가능

연결리스트 vs 이중 연결리스트 vs 이중 원형 연결리스트

• 연결리스트(linked list) - 데이터 접근성이 나쁨
• 이중 연결리스트(doubly linked list) - 데이터 접근성 향상
• 이중 원형 연결리스트(doubly circular linked list)

연결리스트(linked list) - 데이터 접근성이 나쁨 

이중 연결리스트(doubly linked list) - 접근성 향상

이중 원형 연결리스트(doubly circular linked list)

 

ArrayList vs LinkedList - 성능 비교

1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름
2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
3. 중간에 추가하기 - LinkedList가 빠름
4. 중간에서 삭제하기 - LinkedList가 빠름
5. 접근시간(access) - ArrayList가 빠름(자바의 정석 3판 예제)

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

자료구조(data structure) - '배열 기반, 연속적'과 '연결 기반, 불연속적'으로 구성되어 있다.

배열 기반 - 연속적, ArrayList

연결 기반 - 불연속적, linkedList