Linked List와 ArrayList 구조,특징, 비교

1. ArrayList와 LinkedList의 구조

2. ArrayList와 LinkedList의 삽입과 삭제 과정

	① 삽입할 자료만큼  공간을 늘리는 작업을 한다.  ② 삽입할 자료의 위치를 기준으로 기존의 데이터들을 뒤로 or 앞으로 이동하는 연산을 수행한다.  ③ 삽입할 위치에 자료가 입력되면 삽입연산을 마친다.
ArrayList 삽입
	① 삭제할 자료가 위치한 인덱스의 자료를 삭제한다.  ② 삭제한 자료의 인덱스를 기준으로 이후의 자료들을 이동하는 연산을 한다.  ③ List의 맨 마지막은 비어있는 상태로 완료한다.
ArrayList 삭제
	① 추가될 자료의 node를 생성한다.  ② 추가될 자료의 인덱스 이전 node와 추가될 자료 인덱스 이후 node를 설정한다.
LinkedList 삽입
	① 삭제할 노드의 이전 노드와 이후 노드를 연결한다.
LinkedList 삭제

3. ArrayList와 LinkedList의 특징 및 비교

ArrayList 특징

1. n개의 자료를 저장할때 ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장

2. 무작위접근(random access) 가능

3. 사이즈 고정되어 있음 

4. 삽입 시 사이즈를 늘려주는 연산 추가되야 함

5. 삭제 시에는 순차적인 인덱스 구조로 인해 삭제된 빈 인덱스를 채워야 하기 하기 때문에 연산이 추가되어야 함

6. 지속적으로 삭제 되는 과정에서 공간만큼 낭비되는 메모리가 많음

7. 삽입 삭제가 빈번하게 발행하는 프로세스의 경우 좋지 않음

Linked List 특징

1. 연결형태로 연결 가능

2. ArrayList처럼 뒤로 밀거나 채우는 작업 없이 주소만 서로 연결시켜 주면 되기 때문에 추가 삭제가 ArrayList보다 빠르고 용이함.

3. 삽입삭제가 빈번하게 발생되면 Linked List을 사용해 시스템 구현이 바람직함.

4. 순차접근(sequential access)만 가능

5. 단순 LinkedList 는 단방향성을 갖고 있어 인덱스를 이용해 자료를 검색하는 애플리케이션에 적합하지 않음

6. 순차접근도 참조의지역성(한번 참조한 데이터는 다시 참조될 가능성이 높음) 때문에 LinkedList보다 ArrayList가 훨씬 빠름.

7. n개의 자료를 저장할때 LinkedList는 자료들을 저장공간에 불연속적인 단위로 저장

8. LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됨

9. LinkedList는 참조자를 위해 추가적인 메모리를 할당해야함(자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적임)

작업파일 첨부 : 

arraylist, linkedlist.pptx