Linked List 구조의 이해

 

 

Linked List의 개념

 

 

Linked List는 데이터를 저장하는 자료구조로, 각각의 데이터들은 노드(Node)라는 객체로 구성된다. node는 data와 다음 노드를 가리키는 pointer로 이루어져 있다.

 

 

Node로 구성된 Linked List의 구조

 

 

data의 저장과 조작에 index를 활용하는 Array나 Array List와는 달리, 앞 Linked List는 앞 뒤 data의 주소(pointer)를 통해 저장과 조작을 수행한다. 이러한 구조는 Linked List가 삽입, 삭제 과정에서 시간 복잡도상 유리함(O(1))을 가지게 해 주지만, data의 검색과 변경에서는 취약함(O(N), 빅오 표기법 기준)을 보인다.

 

또한 Array와 달리 객체 생성 시점에 data가 저장될 길이를 미리 할당할 필요가 없으며, 동적 크기를 가지므로 길이가 가변적이다. 이와 같은 특징으로 인해 Array에 비해 훨씬 자유롭게 조작할 수 있지만, object type이기에 primitive type인 Array에 비해 속도가 느리다는 단점이 있다.

 

 

Array List와 Linked List의 시간 복잡도 비교

 

 

Linked List는 index를 사용하지 않아 삽입, 삭제 과정에서 나머지 data들을 밀어내거나 당길 필요가 없으므로, 항상 한 번의 작업만 수행하면 된다. 반면 index를 사용하는 Array List는 가장 마지막 위치에 값을 추가하거나 마지막 값을 삭제하는 과정에서는 동일하게 한 번의 작업만 수행하면 되지만, 앞의 index로 갈수록 추가/삭제 과정에서 나머지 data들을 index에 맞춰 모두 뒤로 밀어내거나 앞으로 당겨야 한다. 따라서 빅오 표기법 기준으로 O(N)의 시간 복잡도를 가지게 된다.

 

반면 data의 검색, 변경 과정에서는 Array List의 경우 index를 이용해 한 번의 작업으로 수행할 수 있지만, Linked List는 각 데이터의 상대적 위치를 이용해 절대적 위치를 찾아가야 한다. 따라서 Linked List는 검색 또는 변경 대상에 해당하는 data를 찾기 위해 모든 data를 훑으며 탐색해야 한다. 따라서 이 경우 반대로 Linked List가 빅오 표기법 기준 O(N)의 시간 복잡도를 가지게 된다.

 

이와 같은 차이 때문에 List가 어떤 것으로 구현되느냐에 따라 시간 복잡도에 상당한 영향이 있고, 따라서 실제 개발 과정뿐만 아니라 코딩 테스트에서도 List가 어떤 작업을 자주 수행하느냐에 따라 신중하게 선택애야 할 필요성이 있다.

 

 

Linked List 구조에서의 명칭

 

 

java에서 Collection의 List 인터페이스를 구현하므로, List를 정렬하고 검색하는 데 도움을 주는 java의 유틸리티 클래스인 Collections를 사용할 수 있다. Collections는 Array의 유틸리티 클래스인 Arrays 클래스에 비해 지원 method가 다양하므로, Array에 비해 data의 복잡하고 다양한 조작에 강점을 보인다.

 

 

Linked List의 응용

 

 

• Java에서의 활용 예시

LinkedList<Integer> linkedList = new LinkedList<>();

linkedList.add(5);
linkedList.add(4);
linkedList.offer(3);

System.out.println(linkedList.poll()); // 5
System.out.println(linkedList); // [4, 3]
System.out.println(linkedList.peek()); // 4

System.out.println(linkedList.getFirst()); // 4
System.out.println(linkedList.getLast()); // 3
System.out.println(linkedList.get(0)); // 4
System.out.println(linkedList.contains(3)); // true
System.out.println(linkedList.size()); // 2

System.out.println(linkedList.remove(0)); // 4

System.out.println(linkedList); // [3]
System.out.println(linkedList.getFirst()); // 3
System.out.println(linkedList.get(0)); // 3
System.out.println(linkedList.contains(4)); // false
System.out.println(linkedList.size()); // 1

System.out.println(linkedList.isEmpty()); // false
linkedList.clear();
System.out.println(linkedList.isEmpty()); // true

 

List의 주요 method에 대해 포스팅한 바 있다(https://hellmir.tistory.com/entry/collection-framework%EC%9D%98-interface-%EC%A2%85%EB%A5%98list-Set-Map%EC%99%80-%EC%A3%BC%EC%9A%94-method-%EC%A0%95%EB%A6%AC).

 

collection framework의 interface(List, Set, Map)별 주요 method 정리

 

Linked List는 Deque 인터페이스의 구현 클래스이기 때문에 이전에 다룬 Stack을 구현하는 데 사용할 수 있으며, 특히 Deque 인터페이스는 Queue 인터페이스를 상속하기 때문에 Linked List는 Deque뿐만 아니라 Queue의 모든 메소드를 구현한다. 다만 Linked List의 또 다른 인터페이스인 List가 워낙 다재다능하기 때문에, List의 메소드를 더 많이 사용하면 Deque, Stack, Queue의 기능들을 구현할 수는 있다.

 

그래프의 인접 리스트를 표현하는 데에도 사용될 수 있으며, 이전 포스팅에서 언급한 것처럼 Hash Map의 충돌 문제 해결에도 사용될 수 있다(https://hellmir.tistory.com/entry/Hash-Map-%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4).

 

Hash Map 구조의 이해

 

동적 할당이 가능한 특성을 활용하여 동적 메모리 할당에도 이용된다.