Java ‐ 컬렉션 프레임워크(LinkedList) - thought-corner/Backend-PlayGround GitHub Wiki

노드와 연결

• 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

public class Node {

	Object object; // 가지고 있는 원소
	Node next;     // 어떤 노드를 가리키는지

	public Node(Object object) {
		this.object = object;
	}
}

• 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
• 데이터를 추가할 때 동적으로 필요한 만큼의 노드를 만들어서 연결한다. 배열과 다르게 메모리를 낭비하지 않는다.
• 이렇게 각각의 노드를 연결해서 사용하는 자료 구조를 연결 리스트라고 한다.

직접 구현하는 연결 리스트

• 연결 리스트와 빅오
  • 특정 위치에 있는 데이터를 반환할 때 - O(N)
    • 연결 리스트에서 노드에는 다음 노드에 대한 참조가 있다. 인덱스가 주어진다하더라도 배열과 달리(O(1)), 연결 리스트의 경우 O(N)의 시간 복잡도를 보인다.
    • 특정 위치의 노드를 찾으려면 결국 순차 탐색으로 가야 하기 때문에 결국 O(N)이 된다.
  • 마지막에 데이터를 추가할 때 - O(N)
    • 데이터를 추가하는 연산 자체로만 본다면 O(1)이지만, 실제로는 마지막까지 찾아가야 하기 때문에 O(N)의 시간 복잡도를 가진다.
  • 특정 위치에 있는 데이터를 바꿀 때 - O(N)
    • 위와 마찬가지로 특정 위치까지 찾아가는데 O(N)의 시간 복잡도를 가진다.
  • 인덱스 조회할 때 - O(N)
    • 위와 마찬가지로 특정 위치까지 찾아가는데 O(N)의 시간 복잡도를 가진다.

배열 리스트와 연결 리스트 성능 비교

기능	배열 리스트	연결 리스트
인덱스 조회	O(1)	O(N)
검색	O(N)	O(N)
앞에 추가(삭제)	O(N)	O(1)
뒤에 추가(삭제)	O(1)	O(N)
평균 추가(삭제)	O(N)	O(N)