[Java] 자료구조 Arraylist/LinkedList 특징

개발시에 실제 다루고자하는 데이터의 특징을 파악하고 어떤 인터페이스를 구현할 컬렉션 클래스를 사용해야하는지 잘 알아야 함으로써 각 인터페이스의 특징과 차이점을 잘이해하고 있어야 한다.

 

 

✅컬렉션 프레임웍크 핵심 인터페이스

---

✅ArrayList

ArrayList란 일반 배열을 사용하지만, 일반 배열과 다른점은  맴버변수로 object 배열을 선언하기떄문에 다양한 타입의 객체를  저장할수있다. 

 

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

• ArrayList에 저장된 세 번쨰 데이터를(data[2])를 삭제하는 과정 (1/2).
  list.remove(2);를 호출

1. 삭제할 데이터 아래의 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.
2. 데이터가 모두 한 칸씩 이동 했으므로 마지막 데이터는 null로 변경한다.
3. 데이터가 삭제 되어 데이터의 개수가 줄었으므로 size값을 감소시킨다.(마지막 데이터를 삭제하는 경우에는 1 번의 배열의 복사 과정은 필요없다.

 

• ArrayList에 저장된 객체의 삭제과정(2/2).

ArrayList에 저장된 첫 번쨰 부터 삭제하는 경우 (배열 복사 발생)

 

결과 ==> 전부삭제가 안된다

 

 

---

✅ 배열의 장점과 단점

• 장점
  
  1. 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
     
     
• 단점
  
  1. 배열은 한번 생성하면 크기를 변경할 수 없다.
     -크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사힌 다음, 참조를 변경해야함.
     -크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
     
     
  2. 비순차적인 데이터의 추가,삭제에 시간이 많이걸린다.(배열의 중간에 값을 추가 또는 삭제하는경우)
     -데이터를 추가하거나 삭제하기 위해,다른 데이터를 옮겨야 함. -그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

---

✅배열의 단점을 보안한 LinkedList

• 배열의 단점을 보완하기 위해 나타난 자료구조가 LinkedList이다.
• 연결 리스트(LinkedList)는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

 

 

• 장점

1. 데이터의 삭제: 단 한번의 참조 변경만으로 가능 
2. 데이터 추가:한 번의 Node 객체 생성과 두 번의 참조 변경만으로 가능 

• 단점

1. LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.
   (연결 리스트에 5개의 노드가 있다고 가정하면 세번쨰 노드에 접근하려면 첫 번쨰 노드 부터 차례대로 찾아가야 한다. 배열처럼 한 번에 갈 수 없다.)

 

 

ref -Java의 정석(남궁성)