List - LinkedList

이전 글에서는 배열을 편리하게 다룰 수 있는 ArrayList 에 대해 학습 해보았다.

배열의 끝에서의 데이터, 추가, 제거는 빠르게 처리 가능하나, 처음, 중간에서 동작을 처리할 때는 낮은 처리 속도를 내고 있었다. 이번엔 처음, 중간에서 빠른 작업 처리가 가능한 LinkedList에 대해 알아보자.

 

public class 내맘대로LinkedList{
	private Node first;
    private int size;
    private Node last;
	
    private class Node{
    	private Node next;
        private Object item;
    }
}

 

LinkedList 는 ArrayList와 다르게 Node 라는 인스턴스 멤버를 사용한다.

배열이 책꽂이와 같다고했을 때, Node 는 기차 칸과 같다.

각 노드는, 다음에 이어질 노드의 주소값을 갖는다. (null 이라면 해당 노드가 마지막 노드라는 뜻)

이러한 구조를 통해 중간 노드를 쉽게 추가, 제거할 수 있다.

작업 순서

1. 추가하고 싶은 위치의 이전 노드를 찾는다.

2. 이전 노드의 next에 담긴 값을 추가할 노드의 next에 담는다.

3. 이전 노드의 next에 추가할 노드의 주소값을 담는다.

 

배열과 같이 O(n)의 연산이 발생하는 shift() 를 할 필요가 없다.

다만, LinkedList는 배열의 처음부터 size 정보를 토대로 원하는 위치까지 반복해서 이동해야만 한다.

위치를 찾는데O(n)이 발생한다.. ㅋㅋ

 

하지만!!

위치 찾아 이동하는 연산과, 값을 복붙하는 shift 연산은 성능면에서 월등한 차이가 발생한다.

 

끝에 추가

LinkedList가 첫 Node 를 시작으로 작업 위치까지 이동이 꼭 필요하다?

그렇다면, LinkedList 의 끝에 값을 추가하기 위해선 항상 O(n) 만큼의 이동작업이 필요할까?

 

그렇지도 않다.

자바에서 제공하는 LinkedList는 필드멤버로, lastNode 를 갖는다.

노드를 추가할 때 다음 노드의 참조값이 null이면 마지막 노드란 의미이므로, 해당 노드의 주소값을 lastNode 변수에 에 넣어두면, O(1)의 연산으로 List의 끝에 노드를 쉽게 추가할 수 있다.

 

살짝 혼란스럽다.

 

다음 글에서 ArrayList 와 LinkedList를 비교 해봐야겠다.