[개인공부] List (ArrayList, LinkedList)

---

ArrayList

• ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일하다.
  • Vector는 자체적으로 동기화가 되어있고, ArrayList는 동기화가 안되어있다는 차이점이있다.
• List 인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.
• 데이터(객체)의 저장공간으로 배열을 사용한다.(배열기반)

---

ArrayList의 메서드

• ArrayList() : 기본생성자
• ArrayList(Collection c) :
  매개변수로 어떤 Collection을 주면 Collection에 저장되어 있는 거를 저장하는 ArrayList를 만들 수 있다. Collection끼리 변환할 때 자주 쓰인다
• ArrayList(int initialCapacity) :
  배열의 길이를 늘려주는것이다.

추가하는 메서드

• boolean add(Object o): 저장할 객체를 파라미터로 받으면 그 객체가 ArrayList에 추가된다.
  성공하면 true 반환, 실패하면 false 반환.
• void add(int index, Object element) : 그냥 추가하면 맨뒤에 추가되는데 index를 지정해서 해당 위치에 추가시킬 수 있다.
• boolean addAll(Collectionm c): 컬렉션을 가지고 있는 요소를 ArrayList에 추가
• boolean addAll(int index, Collection c): 그 컬렉션을 어디에 추가할지 지정가능

삭제하는 메서드

• boolean remove(Object o): 저장한거 삭제
• Object remove(int index): 특정위치에 있는거 삭제
• boolean removeAll(Collection c): 컬렉션을 지정해주면 컬렉션 삭제
• void clear(): 어레이리스트에 저장되어있는 모든 객체 삭제

검색하는 메서드

• int indexOf(Object o): 오브젝트(객체)가 몇번째에 저장되어있는지 인덱스를 반환, 못찾으면 -1 반환. 맨앞(0번 인덱스)에서부터 찾는다
• int lastIndexOf(Object O): 맨 뒤부터 객체를 찾는다
• boolean contains(Object o): 특정된 객체가 존재하는지, 존재하면 true, 아니면 false
• Object get(int index): 특정 위치에 있는 객체를 읽어서 반환
• Object set(int index, Object element): 특정 위치에 있는 객체를 변경

그 외 메서드

• List subList(int fromIndex, int tolndex): from~to 사이에 있는 객체들을 뽑아서 새로운 List를 만드는 것.
• Object[] toArray(): ArrayList가 가지고 있는 객체 배열을 반환
• Object[] toArray(Object[] a):
• boolean isEmpty(): ArrayList가 비어있는지 확인하는 메서드
• void trimToSize(): 빈공간 제거하는 메서드
• int size(): ArrayList에 저장된 객체의 갯수 반환

add() ArrayList에는 객체만 저장가능하다. 그러나 기본형으로 넣어도 autoboxing에 의해 참조형으로 자동변환되어 저장된다.

list1.add(5) // 로 넣어도 컴파일 되면서 
list1.add(new Integer(5)) // 로 바꾸어준다.

sort()

contains()

그냥 add()에서

add(int index, Collection c) B, C 가 한칸씩 뒤로 밀리면서 3번 인덱스 자리에 A가 들어간다.

set(int index, Object element)

remove(int index) : 인덱스 값이 1인거 인덱스가 1인 객체를 삭제

remove(new Integer(1)) : 객체가 Integer 타입의 1인거 객체 1을 삭제

retainAll()
get()+contains()+remove() 1. get(i)으로 list2에서 하나씩 꺼낸다.
2. contains()로 꺼낸 객체가 list1에 있는지 확인한다
3. remove(i)로 해당 객체를 list2에서 삭제한다.

ArrayList에 저장된 객체의 삭제과정

• ArrayList에 저장된 세 번째 데이터(data[2])를 삭제하는 과정. list.remove(2);를 호출
  • list.remove(2);는 index가 2인 객체를 말한다.
    삽입은 반대로 1. 한칸 아래로 복사 2. 사이즈값 증가시킴
    💡마지막 데이터를 삭제하는 경우, 1의 과정(배열의 복사)은 필요없다.(데이터를 이동시킬 필요가 없기 때문)

전체삭제가 안되고 데이터가 남음-> 배열복사하니까 느려서 성능 떨어짐
배열 복사안하니까 빠르고 데이터가 다 잘 지워짐

---

---

LinkedList

LinkedList를 알아보기전에, 배열의 장단점 부터 알아보자면,

배열의 장단점

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

• 0번 인덱스나 n번 인덱스를 읽는데 걸리는 시간이 같다.

단점1: 크기를 변경할 수 없다.

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

1. 더 큰/작은 배열을 만들고
2. 데이터 복사
3. 참조 변경

• 크기 변경을 피하기 위해 처음부터 충분히 큰 배열을 생성하게되면 메모리가 낭비된다

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

비순차적이란 배열 중간에 있는 데이터를 말한다.

• 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
  • 하나의 요소를 추가하거나 지우면 데이터가 이동이 되기 때문에 시간이 오래걸린다.
• 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

LinkedList - 배열의 단점을 보완

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결한다(link)
  • 원래 배열은 각 요소가 연속적이다.
• 데이터의 삭제: 단 한 번의 참조변경만으로 가능하다.
  0x200에 다음 요소(노드)의 주소인 0x300이 저장된다. 그다음도 그다음도.. 데이터 하나하나가 연결되어 있다.
  중간에 요소를 삭제하려면 연결만 바꾸어주면 된다. (삭제된건 GC가 알아서 관리하면서 삭제해준다)
• 데이터 추가: 한번의 node 객체 생성과 두 번의 참조 변경만으로 가능.
  새로운걸 만들어서 연결만 바꿔주면됨
  
  

링크드 리스트(linked list)의 단점

• 연결리스트.
• 각 요소가 불연속적이어서 데이터 접근성이 나쁘다.
  • 다음요소로 갈 때 다음요소로는 갈 수 있는데 다음요소가 아닌 다른 요소까지 한번에 갈 수 가 없다.

더블리 링크드 리스트(doubly linked list) 자바는 이걸로 구현되어있다.

• 이중 연결 리스트 = 연결이 두개!
• 접근성 향상 단점은 새로운 요소 추가/삭제시 연결을 2개를 끊어주고 이어줘야해서 시간이 오래걸린다.

더블리 써큘러 링크드 리스트(doubly circular linked list)

• 이중 원형 연결리스트
  99까지 있는 채널에서 99다음으로 가려하면 1로가는 것처럼

—-

ArrayList vs LinkedList 성능 비교

• 순차적으로 추가하는건 데이터 이동이 없으므로 Array가 빠르다, 배열은 한번에 저장공간을 만드는데 linked는 하나 추가할 때마다 새로 객체를 만들어서 연결하기 때문에 느리다
• 순차적으로 삭제도 같은로직!
• 비순차적(중간에)은 링크드가 빠르다. 20배 넘게 차이남! 헉
• 접근 시간은 Array가 빠르다.
  인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
  만 계산하면 되기 때문에