공부의 정리 및 복습을 위한 기록입니다.
오늘은 저번 ArrayList에 이어 list인터페이스의 다른 구현 클래스인 Linkedlist클래스를 정리하려고 한다.
Linkedlist는 배열로써 순차적으로 저장하는 Arraylist와 다르게 비순차적으로 데이터를 저장하며 각 요소는 자신과 연결된 다음 요소에 대한 참조값과 데이터로 구성되어있다.
이해하기 쉽게 다음 사진을 보고 정리를 해보자.
linkedlist의 구조이다. 여기서 curr뒤에 새로운 요소를 삽입 하려고 한다.
위 사진과 같이 새로운 요소가 삽입되면 기존에 curr요소가 가지고있던 다음 요소의 참조값은 새로 삽입된 요소의 참조값을 가지게 된다.
순차적으로 데이터를 저장하고 있는 Arraylist는 삽입이 이루어지면 뒤에있는 요소들을 한 칸씩 미뤄야 하지만 비 순차적으로 저장하여 다음 요소의 참조값을 가지고 있는형태로 구성되는 Linkedlist는 요소의 삽입 시간 복잡도가O(1)로 이루어져 있기 때문에 더 빠른 실행속도를 가지고 있다.
다음은 Linkedlist의 삭제가 이루어 지는 과정이다.
삽입과 마찬가지로 삭제를 하여도 각 요소를 한 칸씩 땅기지 않고 삭제되는 요소와 연결되어있는 전 요소와, 다음 요소가 가지고 있는 참조값만 변경 되기 때문에 삽입과 마찬가지로 O(1)의 시간 복잡도를 가지고있다.
하지만 인덱스로 요소를 찾는 Arraylist와 달리 요소의 참조값을 통해서 순차적으로 찾아가야하는 Linkedlist의 특성 상 삽입과 삭제가 이루어지는 과정에서 삭제할 요소를 찾아가는 과정이 O(n)의 시간 복잡도를 가지게 되기 때문에 꼭 삽입과 삭제에서 무조건 O(1)의 시간 복잡도를 갖지는 않는다. 이 점을 유의하여야 한다.
Linkedlist는 Arraylist와 동일하게 List 인터페이스의 구현 클래스로 사용 방법 및 메서드는 동일하다.
주요 메서드로
add()
remove()
get()
set()
size()
contains() 등이 있다.
조금 더 자세한 메서드 사용 방법은
Arraylist 개념 및 메서드
List 인터페이스의 메서드
위 두 곳에 정리를 해놨으니 참고해서 보면 된다.
사용 방법은 동일 하지만 둘은 전혀 다른 자료구조를 가지고 있기 때문에 혼동하지 않고 적절하게 사용하는것이 좋을 것 같다.
공부하며 정리와 복습을 위해 저장한 기록입니다. 틀린 부분 및 개선할 부분이 있다면 알려주시면 감사하겠습니다 !
