자료구조 - Array vs LinkedList

2019-11-08

Array vs LinkedList

array는 논리적 저장 순서와 물리적 저장 순서가 일치하므로 인덱스(index)로 해당 원소에 접근하는 random access가 가능하며 시간 복잡도는 O(1)이다.

배열의 원소를 삽입하거나 삭제한다면, 인덱스가 보다 큰 모든 배열의 원소들을 shift하는 비용이 발생하고 이 경우 시간 복잡도는 O(n)이다.

linkedlist의 원소들은 자기 자신의 다음 원소만을 기억하므로 이 부분만 값을 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다.

하지만 array와 달리 논리적 저장 순서와 물리적 저장 순서가 불일치하므로 search에 O(n)의 시간이 추가적으로 발생한다.

  • array linkedlist  
    탐색 O(1) O(n)
    삽입 O(n) O(n)
    삭제 O(n) O(n)

LinkedList in Java

import java.util.*; 
  
public class Test 
{ 
    public static void main(String args[]) 
    { 
        // Creating object of class linked list 
        LinkedList<String> object = new LinkedList<String>(); 
  
        // Adding elements to the linked list 
        object.add("A"); 
        object.add("B"); 
        object.addLast("C"); 
        object.addFirst("D"); 
        object.add(2, "E"); 
        object.add("F"); 
        object.add("G"); 
        System.out.println("Linked list : " + object); 
  
        // Removing elements from the linked list 
        object.remove("B"); 
        object.remove(3); 
        object.removeFirst(); 
        object.removeLast(); 
        System.out.println("Linked list after deletion: " + object); 
  
        // Finding elements in the linked list 
        boolean status = object.contains("E"); 
  
        if(status) 
            System.out.println("List contains the element 'E' "); 
        else
            System.out.println("List doesn't contain the element 'E'"); 
  
        // Number of elements in the linked list 
        int size = object.size(); 
        System.out.println("Size of linked list = " + size); 
  
        // Get and set elements from linked list 
        Object element = object.get(2); 
        System.out.println("Element returned by get() : " + element); 
        object.set(2, "Y"); 
        System.out.println("Linked list after change : " + object); 
    } 
}

output

Linked list : [D, A, E, B, C, F, G]
Linked list after deletion: [A, E, F]
List contains the element 'E' 
Size of linked list = 3
Element returned by get() : F
Linked list after change : [A, E, Y]