'list'에 해당되는 글 1건

[List] 

먼저 List 자료 구조는 자료를 순서대로 저장하는 Sequential 한 선형 구조를 뜻한다. 기존의 배열 자료구조에서와 같이 순차적으로 저장되지만 배열에서는 빈 공간이 존재할 수 있었다. 이런 빈공간에서 오는 Memory 낭비를 줄이고자 빈공간이 없게 삭제된 공간은 당겨서 채우는 식으로 구현이 된다.

[ArrayList]

  배열 자료구조에 List 자료 구조의 특성인 빈공간이 없게 구현한 자료구조이다. 원소에 대해 Index로 접근이 가능하고 임의의 Index에 접근할 때 O(1)의 시간복잡도를 가진다.

import java.util.*;

public class test {
    
    public static void main(String[] args){
    	
    	ArrayList<Integer> aList = new ArrayList<>();
    	
    	for(int i = 0; i < 5; i++) {
    		aList.add(10*i);
    	}
    	System.out.print(aList+"\n");
    	System.out.print(aList.get(3));
    }
}

[LinkedList]

  연결리스트라고 불리는 구조로 물리적으로는 순차적으로 존재하지는 않지만 논리적으로는 순차적인 구조를 가진다.

위 다이어그램과 같이 각 노드(node)들이 순차적으로 연결되어 있고 노드는 자료 + 다음 노드를 가리키는 링크로 구성된다. 즉, 물리적으로 연결된 것이 아니라 Link를 통해 순차적으로 연결된 자료 구조이다.

ArrayList 와 차이는 Index를 통한 직접 접근이 불가능해 임의의 위치의 원소를 찾기 위해서는 O(n)의 시간복잡도가 필요하다.

import java.util.*;

public class test {
    
    public static void main(String[] args){
    	
    	LinkedList<Integer> aList = new LinkedList<>();
    	
    	for(int i = 0; i < 5; i++) {
    		aList.add(10*i);
    	}
    	System.out.print(aList+"\n");
    	System.out.print(aList.get(3));
    }
}

[Method의 시간복잡도 분석표]