-
5. Collection 프레임워크 (ArrayList vs LinkedList)프로그래밍언어/Java(초급) 2020. 3. 29. 17:51
자료구조란?
프로그램을 작성하는 과정에는 여러데이터가 필요 하다. 예를들어100명의 학생 성적을 처리한다고 할때 각각의 성적 값을 변수에 할당한다면100개의 변수가 필하고 이런경우 배열을 이용하면하나의 변수명으로 100개의 데이터를 처리할 수 있게 된다.
자료구조는 컴퓨터 프로그램에서 데이터를 처리하기 위해 만든 구조로Array, List, Map이 대표적인 형태 이며 이 외에 프로그램 언어에 따라Tuple, Dictionary등을 사용하기도 한다.
리스트(List)
배열과 유사한순차적인 자료구조를 제공 한다. 객체지향 프로그램언어에는 보통 List 자료구조가 기본적으로 제공되며 그렇지 않을 경우 직접 자료구조를 구현하거나 구현된 라이브러리를 사용해야 한다. 데이터 접근을 위해 인덱스를 사용해야 하는 점은 배열과 같지만 배열의 모든문제점을 해결하고 있다.
- 데이터 크기가 고정되지 않음.
- 데이터를 다루기 위한 여러 방법이 제공됨.
- 리스트의 데이터는 서로 다른 타입일 수 있음. -> 일관된 처리가 어려워보통은 동일하게처리함.
- 배열 중간에 값을 추가하거나 삭제하기 쉬움.
- 특정 데이터가 포함되어 있는지 확인은 가능하나 검색을 위해서는 별도 구현이 필요.
Linked List는 현재 데이터에 다음데이터를 읽을 수 있는 정보를 추가한 것으로 불연속적으로 존재하는 데이터를 서로 연결할 수 있는 방법을 제공 하며Double Linked List는 이전과 다음 데이터 정보를 모두 가지고 있는 형태이며 자바의 경우LinkedList클래스가 제공되는데 실제로는Double Circular Linked List(순환구조가 추가된 Double Linked List) 형태를 구현해 둔 것이다.
02: 컬렉션 프레임워크(Collection Framework)
컬렉션은 데이터 저장, 그리고 이와 관련 있는 알고리즘을 구조화 해 놓은 프레임 워크이다. 위에서 언급한 자료구조와 알고리즘을 클래스로 구현해 놓은것 정도로 생각해 놓으면 된다. 이와 유사하게 컬렉션 프레임 워크를 구성하는 클래스들은 많은 양의 인스턴스를 다양한 형태로 저장하는 기능을 제공하고 있다. 따라서 자료구조와 알고리즘을 잘 몰라도 자바의 컬렉션 프레임워크를 활용하면 다양하고 효율적으로 인스턴스의 저장이 가능하다.
- Collection 인터페이스와 Map<k,v> 인터페이스로 나뉜다.
List 인터페이스와 이를 구현하는 제네릭 클래스 ArrayList,LinkedList
-
동일한 인스턴스의 중복 저장을 허용한다.
-
인스턴스의 저장 순서가 유지된다
ArrayList
import java.util.ArrayList; class IntroArrayList { public static void main(String[] args){ ArrayList<Integer> list = new ArrayList<Integer>(); /* 데이터의 저장*/ list.add(new Integer(11)); list.add(new Integer(22)); list.add(new Integer(33)); /*데이터의 참조*/ System.out.println("1차 참조"); for(int i =0; i<list.size();i++){ System.out.println(list.get(i)); } /*데이터의 삭제*/ list.remove(0); System.out.println("2차 참조"); for(int i =0; i<list.size();i++){ System.out.println(list.get(i); output ====================== 1차 참조 11 22 33 2차 참조 22 33
배열과 상당히 유사하지만 데이터의 저장을 위해서 인덱스 정보를 별도로 관리할 필요가 없고, 데이터의 삭제를 위한 추가적인 코드의 작성이 전혀 필요 없다.저장되는 인스턴스의 수에 따라서 그 크기도 자동으로 늘어나기 때문에 배열과 달리 길이를 고민하지 않아도 된다.
용량을 증가시키는 과정에서 수반되는 연산으로 인해 성능에 부담이 될수도 있다. 데이터의 저장이 예상될 경우 초기값을선언하여 불필요한 연산을 줄일 수 있다.
다양한 ArrayList 사용
class Ideone { public static void main (String[] args) throws java.lang.Exception { List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)); System.out.println("numbers: " + numbers.toString()); /* 데이터 조건에 맞게 삭제*/ numbers.removeIf(n -> (n == )); System.out.println("numbers(after removeIf): " + numbers.toString()); /* 데이터 전부 삭제*/ numbers.removeAll(numbers); System.out.println("numbers(after removeAll): " + numbers.toString()); /*데이터 변경 */ List<Integer> numbers2 = new ArrayList<>(Arrays.asList(10,10, 10, 20, 3, 4, 5, 6, 7, 8, 9)); Collections.replaceAll(numbers2,10,100); System.out.println("numbers2(after replaceAll): " + numbers2.toString()); numbers2.set(100,-100); numbers2.set(20,-20); numbers2.set(3,-3); System.out.println("numbers2(after set): " + numbers2.toString()); } } output ====================== numbers: [1, 2, 3, 4, 5, 6, 7, 8, 9] numbers(after removeIf): [1, 2, 3, 4, 5, 6, 7, 8, 9] numbers(after removeAll): [] numbers2(after replaceAll): [100, 100, 100, 20, 3, 4, 5, 6, 7, 8, 9] numbers2(after set): [-100,-100,-100,-20,-3,4,5,6,7,8,9,]
LinkedList
import java.util.ArrayList; class IntroArrayList { public static void main(String[] args){ LinkedList<Integer> list = new LinkedList<Integer>(); /* 데이터의 저장*/ list.add(new Integer(11)); list.add(new Integer(22)); list.add(33); /*데이터의 참조*/ System.out.println("1차 참조"); for(int i =0; i<list.size();i++){ System.out.println(list.get(i)); } /*데이터의 삭제*/ list.remove(0); System.out.println("2차 참조"); for(int i =0; i<list.size();i++){ System.out.println(list.get(i); output ====================== 1차 참조 11 22 33 2차 참조 22 33
데이터의 저장,참조 및 삭제기능의 활용방법만 놓고보면 차이는 없다. 그러나 내부적으로 인스턴스를 저장하는 방식에서 큰 차이를 보인다. 우선 ArrayList는 그 이름이 의미하듯이 배열을 기반으로 하는데 내부적으로 배열을 이용해서 인스턴스의 참조 값을 저장한다.
- 저장소의 용량을 늘리는 고정에서 많은 시간이 소요된다 ArrayList의 단점
- 데이터의 삭제에 필요한 연산과정이 매우 길다. ArrayList의 단점
- 데이터의 참조가 용이해서 빠른 참조가 가능하다. ArrayList의 장점
배열의 용량을 늘리는 것은 인스턴스의 생성과 기존데이터의 복사가 필요한 작업이다. 따라서 부담이 클수 있는 잡업이다. 그리고 데이터의 삭제 작업 역시 간단 하지가 않다. 첫번째 위치에 저장된 데이터를 지우고자 할 경우에, 그 뒤에 저장된 데이터들을 한칸씩 앞으로 이동시켜야 하는 불편함이 따른다. 때문에 ArrayList의 삭제는 많은 연산이 수반될 수 있다. 하지만 참조는 인덱스 값을 사용하여 바로 접근이 가능하다.
이해를 돕기위한 LinkedList
class Box<T> { public Box<T> nextBox; T item; public void store(T item) {this.item=item;} //인스턴스를 사용하기위한 참조변수 public T pullOut() {return item;} } class SoSimpleLinedListImpl { public static void main(String[] args) { Box<String> boxHead = new Box<String>(); boxHead.store("First String"); boxHead.nextBox = new Box<String>(); boxHead.nextBox.store("Second String"); boxHead.nextBox.nextBox = new Box<String>(); //상자를 연결하여 생성한다. boxHead.nextBox.nextBox.store("Third String"); Box<String> tempRedf; /*두번째 박스에 담긴 문자열 출력과정*/ tempRef = boxHead.nextBox; System.out.println(tempRef.pullOut()); /*세번째 박스에 담긴 문자열 출력과정*/ tempRef = boxHead.nextBox.nextBox; System.out.println(tempRef.pullOut()); } output========================= Second String Third String
저장소를 늘리는 과정이 매우간단하며 마치 블록을 하나 연결하는 것과 마찬가지로 과정이 간단하다. 그리고 데이터의 삭제 역시 매우 간단하다. 중간에 위치한 상자하나를 삭제하는 것과 같다. 하지만 데이터의 참조를 위해서는 연결되어 있는 상자들을 통해서 이동해야 하기 때문에 불편하다.
- 저장소의 용량을 늘리는 과정이 간단하다.
- 데이터의 삭제가 매우 간단한다.
- 데이터의 참조가 다소 불편하다.
ArrayList, LinkedList 객체를 생성하고 다양한 메서드를 사용해 데이터를 다루고 정렬하기
public class ListTest { public static void main(String[] args) { // create new List List<String> l1 = new ArrayList<>(); List<String> l2 = Arrays.asList("one", "two"); List<String> l3 = List.of("three", "four"); // add data to List l1.addAll(l2); l1.addAll(1, l3); l1.add("five"); System.out.println("## element in List"); System.out.println(l1); // create new LinkedList and add data LinkedList<String> llist = new LinkedList<>(); llist.addAll(l2); llist.addAll(1, l3); llist.add("five"); System.out.println("## element in LinkedList"); System.out.println(l1); // access data with index System.out.println("## first element: " + l1.get(0)); System.out.println("## last index of three: " + l1.lastIndexOf("three")); // change data in List l1.set(0, "zero"); System.out.println("## after set(): element in LinkedList"); System.out.println(l1); // Descending sort Collections.sort(l1); System.out.println("## Descending sort of l1"); System.out.println(l1); // Ascending sort l1.sort(new Comparator<Object>() { @Override public int compare(Object o1, Object o2) { return o2.toString().compareTo(o1.toString()); } }); System.out.println("## Ascending sort of l1"); System.out.println(l1); // Ascending sort with stream api System.out.println("## Ascending sort with stream api"); l1.stream().sorted((o1, o2) -> o2.toString().compareTo(o1.toString())).forEach(System.out::println); } }
IterAtor을 이용한 인스턴스의 순차적 접근
- boolean hasNext() 참조할 다음번 요소가 존재하면 true를 반환
- E next() 다음 번 요소를 반환
- void remove() 현재 위치의 요소를 삭제
import java.util.Iterator; import java.utill.LinkedList; class IteratorUsage { public static void main(String[] args) { LinkedList<String> list= new LinekdList<String>(); list.add("First"); list.add("Second"); list.add("Third"); list.add("Fourth); Iterator<String> itr = list.iterator(); //이터레이터 사용 System.out.println("반복자를 이용한 1차 출력과 \"Third\" 삭제"); while(itr.hasNext())//참조할 요소가 존재할때 까지 { String curStr = itr.next(); Sysem.out.println(curStr); if(curStr.compareTo("Third")==0) // 비교하는 문자열이 같을경우에 == 0 , 숫자일경우 비교차이만큼의 숫자 리턴 itr.remove(); } System.out.println("삭제 후 반복자를 이용한 2차출력"); iterator<String> itr = list.iterator(); while(itr.hasNext())//참조할 요소가 존재할때 까지 { System.out.println(itr.next()); } } } output=================================== 반복자를 활용한 1차 출력과 Third 삭제 First Second Third Foruth 반복자를 활용한 2차출력 First Second Foruth
refrence
https://docs.oracle.com/javase/8/docs/api/index.html
'프로그래밍언어 > Java(초급)' 카테고리의 다른 글
2. OOP(Object Oriented Programming) 상속 (0) 2020.04.02 1. OOP(Object Oriented Programming) 캡슐화 (0) 2020.04.01 4. StringBuilder & StringBuffer 클래스 다루기 (0) 2020.03.27 3. Java 문자열(String) 다루기 (0) 2020.03.27 1. BufferReader VS Scanner 차이점 (0) 2020.03.27