[JAVA의 정석]LinkedList

이 글은 유튜브 '자바의 정석 - 기초편'을 보고 정리한 글입니다. 

 

 

📂content

1. 배열의 장단점

⚝  장점

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

배열은 연속적이다. 
예를 들어, int배열이라고 하면 하나가 4btye이다.
그렇다면 3이라는 데이터를 읽을려고 한다면, 0x100 + 4 * 2를 하면 된다. 
즉, 배열주소+ 배열 요소 크기 * 인덱스(n) = 내가 원하는 주소를 알 수 있다. 
(-> n+1번째 요소를 알 수 있음. n+1인 이유는 index가 0부터 시작하므로 ) 

 

 

 

⚝  단점

1. 크기를 변경할 수 없다. 

- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함. (코드로 작성은 못 해도 설명은 해야함. )

    ① 더 큰 배열 생성

    ② 기존 내용 복사

    ③ 참조 변경 

   

 

2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다. 

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

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

    비순차적 => 중간에 있는 데이터 같은 것들 

 

 

 

 

 

2. LinkedList -  배열의 단점을 보완 

- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)

배열(Array)

0x104, 0x108....처럼  데이터가 붙어있다. 

 

 

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

- 각 요소가 어디에 있는지 알 수 가 없다. 
- 요소 하나를 `Node`라고 한다. Node 클래스를 보면 Node는 다음 노드이고, Object는 데이터이다. 
- 다음 요소(노드)의 주소인 0x300을 저장한다. 
- Array(배열)은 상자와 비슷하고, 리스트(List)는 기차와 비슷하다. 

 

 

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

4를 추가함.

 

 

● 링크드 리스트(linked list) - 연결리스트. 데이터 접근성이 나쁨

내 다음만 알고 있다. 한 번에 내가 원하는 장소로 갈 수가 없다.  

 

 

● 더블리 링크드 리스트(doubly linked list) - 이중 연결리스트, 접근성 향상 

 

 

 

연결이 2개임. 참조 next와 previous 2개를 가지고 있다. 

 

 

● 더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트 

다른 리스트를 보면 마지막 값이 null이다. 이것을 활용한 것! 

 

 

 

 

 

3. ArrayList vs LinkedList -  성능 비교 

① 순차적으로 데이터를 추가 / 삭제 - ArrayList가 빠름

② 비순차적으로 데이터를 추가 / 삭제 - LinkedList가 빠름

③ 접근시간(access time) - ArrayList가 빠름

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

 

 

✎ 정리

컬렉션	읽기(접근 시간)	추가 / 삭제	비고
ArrayList	빠름	느림	순차적인 추가삭제는 더 빠름. 비효율적인 메모리 사용 (성능을 높이려고 배열을 크게 잡아서)
LinkedList	느림	빠름	데이터가 많을수록 접근성이 떨어짐

 

 

 

 

 

 

📣 comment

ArrayList와 List는 다르다. 

이 둘의 가장 큰 차이점은 초기화시 크기가 가변인지 불변인지이다. 

ArrayList는 크기가 가변적이지만, List는 크기가 불변이다. 

우리가 알고리즘 테스트를 볼 때 주로 사용했던 것은 List이다. 

//배열(Array)
int arr = new int[4];

import java.util.ArrayList;
//ArrayList
ArrayList<Integer> list = new ArrayList<>();

 

 

 

 

출처

https://www.youtube.com/watch?v=oJlCC1DutbA&list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp