LinkedList

ArrayList 와 같은 배열 타입의 단점을 보완한 자료구조

극복한 단점 = 잠재적 메모리 낭비

 

데이터를 담는 자료 구조로서

연쇄되는 Node  를 사용함.

 

기본 구조

class LinkedList{

private Node first;

private Node last;

}

 

class Node{

 Obejct value;

 Node next;

 Node previous;

}

 

모양

노드 - 노드 - 노드 - 노드 - 노드 - 노드

자료   자료   자료   자료  자료    자료

 

빅오 표기법

추가

처음 - O(1)

중간 - O(n)

마지막 - O(1)

 

조회

LinkedList 에는 index가 없음.

처음이든, 끝이든 시작점을 잡고 특정 위치가 나올 때까지 이동해야하므로 O(n) 임.

 

 

ArrayList 와 다르게 처음, 중간, 끝에 새로이 자료를 추가할 때  O(1) 연산으로 해결 됨.

이유는 몹시 단순함.

배열에서는 데이터 추가, 삭제 시 shift연산(O(n)) 이 강제적으로 발생함.

 

반면, LinkedList 는 Node 객체끼리 참조값을 갖고 있어, 링크만 갈아끼워주면 shift 연산이 있을 필요가 없음.

애초에 shift연산이 발생할 자료 구조가 아님.

 

그러나, 특정 데이터를 찾기 위해 O(n)의 연산이 필요하며,

이동할 때, 객체 주소를 계속해서 갈아끼우며 탐색함.

 

또, Node 자체가 객체이므로, 자료 수가 많을수록 메모리 낭비가 심해짐.

 

그래서, 중간에서 연산이 정말정말 많이 발생하는 게 아니면,  LinkedList 보단 ArrayList가 좀 더 낫다고 함.