JAVA 자료구조 < List > 1)ArrayList, 2)LinkedList

 

 

 

* List Interface

• ArrayList, LinkedList의 구현체
• Vector, Stack은 지금은 사용하지 않지만 호환성을 위해 남겨둔 Class
• 순서가 있는 데이터의 집합
• 인덱스로 객체에 접근 할 수 있다.(공통)

 

 

 

* List 주요기능

1. 삽입: List.add(값);
2. 중간 삽입: List.add(index, value); : index: 중간에 넣을 인덱스(배열 인덱스),value: 중간에 넣을 값. (중간에 값을 넣을 경우 중간에 넣은 값 이후에 값들은 한 칸씩 밀리게 됩니다.
3. 치환: List.set(index, value); : 중간 삽입과 비슷하게 index는 치환할 값 자리에 인덱스이고 value는 치환할 자리에 값이다.
4. 삭제: List.remove(index); : 인덱스 위치에 있는 값을 삭제한다.
5. 전체 삭제: List.clear(); 모든 요소를 삭제
6. 출력: List.get(index) : 인덱스 위치에 있는 값을 출력
7. 사이즈: List.size() : 리스트에 크기를 알 수 있다.

 

 

* List 특징

• 특정 요구사항이 없을 경우, 요소의 추가는 LIST 제일 마지막에 추가
• 데이터간 사이에 공백 비허용 => GC(Garrbage Collection/가비지 컬렉터)으로 배열 관리(GC : JVM 의 heap영역에서 동적으로 할당했던 메모리 영역 중 필요 없게 된 메모리 영역을 주기적으로 삭제하는 프로세스) 를 통해 메모리 누수(Memory Leak)문제 방지 (GC단점 : 1. 개발자가 메모리 해제 시점을 파악하기 어려움, 2. GC가 동작하는 동안에는 다른 동작을 멈추기 때문에 오버헤드가 발생 *오버헤드: 프로그램의 실행흐름에서 나타나는 현상중 하나, 프로그램의 실행흐름 도중에 동떨어진 위치의 코드를 실행시 추가적으로 시간, 메모리, 자원이 사용되는 현상)
• 중복 허용
• 크기 조절 가능
• 컬렉션 인터페이스중 하나

 

 

 

 

* 포괄적인 List 개념 중 자바에 해당하는 List개념 ?

• 순서가 있는 엘리먼트의 모임(배열과는 다르게 빈 엘리먼트는 절대 허용x)
• 배열이 지닌 인덱스라는 장점 대신 빈틈없는 데이터의 적재라는 장점
• 리스트에서 인덱스는 몇 번째 데이터인지 순서의 의미
• ' java에서는 빈 엘리먼트를 허용하는 경우가 있음' 이라는 표현이 간혹 검색했을 때 뜨는데, 사실상 빈값이 아니어야 한다. 값이 없다면 ArrayList든 LinkedList든 어차피 당겨지기 때문에 어차피 null처럼 값이 설정되어 있어야 한다
• 일시적 메모리 공간 차지.(불연속적 메모리 공간 차지라는 표현도 뜨는데 ,,잠깐 사용한다고 생각하는게 나은 것 같다.)
• 포인터를 통한 접근(C나 C++ 에는 포인터라는 개념이 존재하지만 Java에는 포인터라는 개념을 사용하지 않는다. 비슷한 개념으로 참조라는 것을 사용한다. 하지만 둘은 다른 개념이다. 그 둘의 차이점에 대해 일단 스킵)
• (순서o, 정렬 x) 순차성을 보장하지 못하기 때문에 공간적 지역성(spatial locality) 보장이 되지 않아서 cache hit이 어렵다. (데이터 갯수를 딱 정해서 자주 사용될 목적이면 array가 더 좋다.그런데, 이 내용은 컴퓨터 공학에 해당해서 스킵)

따라서~ List는 ArrayList와 LinkedList 2종류만!

Class	Base Class	Base Interface	순서 보장	정렬 여부
ArrayList	AbstractList	List	o	x
LinkedList	AbstractSequentialList	List , Deque	o	x

여기에서 순서 보장은 3, 2, 7 처럼 배열에 적어둔 순 대로 => 3, 2, 7 출력
그런데,
정렬 보장은 3, 2, 7 => 2, 3, 7 처럼 내림차순이던 오름차순같은 기준이 적용되어 출력됨을 의미








각 종류별 특징 기억해보기!

* ArrayList

1. 사용하는 이유 : 기본 배열(int[ ] a = new int[ ]) 사용시 해당 인덱스 값이 다 차서 값을 넣지 못하거나,  인덱스를 다 못 채워서 메모리가 낭비될 수 있는 점 때문에 ArrayList를 사용한다. (배열과 매우 유사하지만 배열은 배열 선언 시 크기도 같이 지정해 줘야 하는데,  ArrayList는 크기를 지정하지 않아도 되며 추가될 때마다 크기가 정해집니다.)
2. 요소를 순차적으로 추가
3. 단점: 객체의 삽입 / 삭제가 자주 있을 때 ArrayList는 비효율적이다. 중간 값을 수정할 때 인덱스 값을 수정하고 그 부분 부터 순서에 맞게 다시 채워야 하기 때문이다.

* LinkedList

1. 하나의 리스트에는 다음 리스트와 이전 리스트의 주소들이 서로 연결되어 있습니다.
2. LinkedList는 index로 값을 저장하지 않고, 연결된 객체(노드)들의 주소 값을 가지고 있기 때문에 객체의 삽입 / 삭제가 ArrayList보다 빠르다.

ArrayList&nbsp; vs LinkedList

 

 

 

<참고 티스토리 >

https://jinyoungchoi95.tistory.com/9

[JAVA] ArrayList 직접 구현하기

https://velog.io/@sunnamgung8/%EC%9E%90%EB%B0%94List%EC%BB%AC%EB%A0%89%EC%85%98

[자바]List(컬렉션)