Java - ArrayList, LinkedList

❕ 배열을 사용할 때 흔히 발생하는 에러인 ArrayIndexOutofBoundsException.

배열을 선언할 때 배열의 크기를 지정하기 때문에, 크기에 벗어나면 에러 발생.

import java.util.Arrays;


public class Main{
  public static void main(String[] args){
    String[] classGroup={"a","b","c","d"};
    int[] gradeGroup=new int[4];

    
    for(int i=0;i<gradeGroup.length;i++){
      gradeGroup[i]=i;
    }

    for (int i=0;i<classGroup.length;i++){
      System.out.println(classGroup[i]);
    }

    System.out.println(Arrays.toString(gradeGroup));//[0, 1, 2, 3]
	  
		for(int i:gradeGroup){
      System.out.println(i);
    }
		
		int[][] myNumbers={{1,2,3,4},{5,6,7}};
    for(int i=0;i<myNumbers.length;i++){
      for(int j=0;j<myNumbers[i].length;j++){
        System.out.println(myNumbers[i][j]);
      }
    }  
  }
	
}

JCF(Java Collections Framework)

이러한 문제를 해결하는 방법으로는 자바에서 제공하는 Java Collections Framework가 있다. Collection이란 데이터의 집합, 그룹을 말하고, JCF는 이러한 데이터, 자료구조인 컬렉션과 이를 구현하는 클래스를 정의하는 인터페이스를 제공한다. 이 기능을 이용하면 배열을 유연하게 사용가능.

Collection인터페이스는 List, Set, Queue로 크게 3가지 상위 인터페이스로 분류할 수 있다. 그리고 Map의 경우, Collection 인터페이스를 상속받고 있지는 않으나, Collection으로 분류됨.

 

 

Collection 인터페이스의 특징

1. Set 인터페이스

     HashSet : 가장 빠른 임의 접근 속도, 순서 예측 불가

     TreeSet : 정렬 방법을 지정할 수 있음

2. List 인터페이스

     LinkedList : 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용
                         (스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰임)

     Vector : 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 X.

     ArrayList : 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어남.

3. Map 인터페이스

    Hashtable : HashMap보다는 느리지만 동기화 지원, null 불가

    HashMap : 중복과 순서가 허용되지 않으며 null값이 올 수 있다.

    TreeMap : 정렬된 순서대로 key, value를 저장하여 검색이 빠름.

 

ArrayList

배열을 이용해서 List를 만드는 방법. 특정 인덱스에 값을 추가할 경우, 기존의 data를 옆으로 밀고, 빈 공간에 삽입. 따라서 추가하거나 삭제할 때마다 데이터를 이동해야 한다.(시간이 많이 소요). 그러나 값을 가져올 때(조회)는 빠르다.

iterator는 ArrayList, HashSet과 같은 컬렉션을 반복하는데 사용할 수 있는 객체.

import java.util.ArrayList;
import java.util.Iterator;

public class Main{
  public static void main(String[] args){
    ArrayList<String> list=new ArrayList<>(Arrays.asList("h","e","l","l","o"));
    System.out.println(list);//[h, e, l, l, o]

    ArrayList<Integer> numbers=new ArrayList<>();
    for(int i=0;i<4;i++){
        numbers.add(i,i*10); //위치, 값
    }
    System.out.println(numbers);//[0, 10, 20, 30]
    //삭제
    numbers.remove(2);
    System.out.println(numbers);//[0, 10, 30]
    //조회
    System.out.println(numbers.get(2));//30
    //크기
    System.out.println(numbers.size());//3

    //Iterator
    Iterator it=numbers.iterator();
    while(it.hasNext()){
        int value=(int)it.next();
        System.out.print(value+" ");//0 10 30
    }

    System.out.println();

    //for-each
    for(int value:numbers){
        System.out.print(value+" ");//0 10 30
    }
    System.out.println();
      
    //ArrayList 뒤집기
    Collections.reverse(list);
    System.out.println(list);//[o, l, l, e, h]
    
  }
}

LinkedList

이 클래스는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다. 데이터는 포인터와 주소를 사용하여 연결한다. 각 데이터는 노드라 불리며, 배열에서 자주 삽입, 삭제가 일어나는 경우 유리하다. 하지만 검색에 있어서는 ArrayList보다 느리다.

자바로 구현한 LinkedList

import java.util.ArrayList;
import java.util.Iterator;


class LinkedList{
  private Node head;
  private Node tail;
  private int size=0;
  
  private class Node{
    private Object data;
    private Node next;
    public Node(Object input){
      this.data=input;
      this.next=null;
    }
    public String toString(){
      return String.valueOf(this.data);
    }
  }
    
  public void addFirst(Object input){//head에 data 추가
    Node newNode=new Node(input);
    newNode.next=head;
    head=newNode;
    size++;
    if(head.next==null){//node가 1개
        tail=head;
    }
  }

  public void addLast(Object input){//tail에 data 추가
    Node newNode=new Node(input);
    if(size==0){
        addFirst(input);
    }else{
      tail.next=newNode;
      tail=newNode;
      size++;
    }
      
  }

  public Node node(int index){//node 탐색
    Node x=head;
    for(int i=0;i<index;i++){
      x=x.next;
    }
    return x;
  }

  public void add(int index, Object input){//중간에 추가
    if(index==0){
      addFirst(index);
    }else{
      Node temp1=node(index-1);
      Node temp2=temp1.next;
      Node newNode=new Node(input);
      temp1.next=newNode;
      newNode.next=temp2;
      size++;
      if(newNode.next==null){//마지막 노드라면
        tail=newNode;
      }
    }
  }

  public String toString(){//리스트 전체 출력
    if(head==null){
      return "";
    }
    Node temp=head;
    String str="[";

    while(temp.next!=null){
      str+=temp.data+", ";
      temp=temp.next;
    }
    str+=temp.data;
    return str+"]";
  }

  public Object removeFirst(){
    Node temp=head;
    head=head.next;
    Object returnData=temp.data;
    temp=null;
    size--;
    return returnData;
  }

  public Object remove(int index){
    if(index==0){
      return removeFirst();
    }
    Node temp=node(index-1);
    Node todoDeleted=temp.next;
    temp.next=temp.next.next;
    Object returnData=todoDeleted.data;
    if(todoDeleted==tail){
      tail=temp;
    }
    todoDeleted=null;
    size--;
    return returnData;
  }

  public Object removeLast(){
    return remove(size-1);
  }

  public int size(){
    return size;
  }

  public Object get(int index){
    Node temp=node(index);
    return temp.data;
  }

  public int indexOf(Object data){
    Node temp=head;
    int index=0;
    while(temp.data!=data){
      temp=temp.next;
      index++;
      if(temp==null){
        return -1;
      }
    }
    return index;
  }

  
}

public class Main{
  public static void main(String[] args){
   LinkedList numbers=new LinkedList();
    numbers.addFirst(30);
    numbers.addLast(10);
    System.out.println(numbers.node(0));
    numbers.add(1,15);
    System.out.println(numbers);//[30, 15, 10]
    System.out.println(numbers.removeFirst());
    System.out.println(numbers);//[15, 10]
    System.out.println(numbers.remove(0));
    System.out.println(numbers);//[10]
    System.out.println(numbers.size());//1
    System.out.println(numbers.get(0));//10
    System.out.println(numbers.indexOf(10));//0
    numbers.addLast(20);
    numbers.addLast(30);
    
    
  }
}

내장된 LinkedList 사용해보기

import java.util.LinkedList;
import java.util.Iterator;

class Main {
  public static void main(String[] args) {
    LinkedList<String> cars=new LinkedList<>();
    cars.addFirst("Volvo");
    cars.addLast("BMW");
    cars.add(1,"Ford");

    for(String c:cars){
        System.out.print(c+" ");//Volvo Ford BMW
    }

    System.out.println();

    Iterator it=cars.iterator();
    while(it.hasNext()){
        String c=(String)it.next();
        System.out.print(c+" ");//Volvo Ford BMW
    }
  }
}

cf.

java.util 패키지 : Java의 java.util 패키지(Package)는 Java 프로그래밍에 유용한 클래스들을 모아둔 것으로 대표적인 클래스로는 날짜와 관련된 Date, Calendar 가 있으며, 자료구조와 관련된 Collection 프레임워크 관련 클래스들이 포함되어 있다.

java.util 패키지 포함되는 클래스들 : 

AbstractCollection, AbstractList, AbstractSequentialList, LinkedList, ArrayList, Vector, Stack, AbstractSet, HashSet, LinkedHashSet, TreeSet, AbstractMap, HashMap, LinkedHashMap, TreeMap, Arrays, BitSet, Calendar, GregorianCalendar, Collection, Date, Dictionary, Hashtable, Properties, EventObject, Locale, Observable, Random, Scanner, StringTokenizer

 

Java - 인코덤, 생물정보 전문위키

 

참고)

https://gangnam-americano.tistory.com/41

https://crazykim2.tistory.com/566