[국비학원 기록/자바] 연결 리스트(Linked List) 종류, 구현, 노드 중간 데이터 추가

수업 시간에 Linked List 숙제를 내주셨는데 또,,또,,그 사이에 까먹어서

자바의 정석으로 복습했다.

 

배열의 장단점

-장점 : 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근 시간, access time)이 짧다.

-단점 : 크기를 변경할 수 없다, 비순차적인 데이터의 추가&삭제에 시간이 많이 걸린다. (비용이 많이 든다.)

 

★배열에 저장공간이 부족하면?

1. 더 큰 배열 생성 2. 복사 3. 참조 변경

=>누가 물어봤을 때 코드는 못짜도 대답할 수 있을 정도로 외우기.

 

연결 리스트(Linked List)

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

-장점 : 데이터가 메모리상 연속된 위치에 저장되지 않아도 되며 일반적으로 떨어진 영역에 저장됨.

         메모리 관리 용이, 데이터가 입력될 때마다 새로운 메모리 주소에 값을 할당하고 이전 자료와 연결해줌.

         노드의 삽입과 삭제가 용이하다.

-단점 : 흩어져 저장되므로 처음부터 순서대로 따라가야 원하는 데이터에 접근할 수 있다. (임의로 액세스를 허용할 수 없다.)

          접근 속도가 느리다, 중간 노드 연결이 끊어지면 다음 노드를 찾기 힘들다.

 

ArrayList vs LinkedList 비교

1. 순차적으로 데이터를 추가&삭제 : ArrayList가 빠름. (읽기가 빠름)

2. 비순차적으로 데이터를 추가&삭제 : LinkedList가 빠름. (추가, 삭제가 빠름)

3. 접근 시간 : ArrayList가 빠름.

 

연결 리스트(LinkedList) 구현

1. 노드 생성

2. 데이터 추가

3. 노드 중간에 데이터 추가

4. 테스트

- 아무것도 add하지 않았을 때 : 출력할 내용이 없습니다.
- A,B,C 순서대로 ADD했을 때 : A->B->C
-2번 인덱스 다음 D 추가 : A->B->D->C
-1번 인덱스 다음 E 추가 : A->E->B->D->C