자료구조 및 알고리즘- List 리스트

리스트는 선형적인 자료구조로 데이터를 일렬로 늘여놓은 형태이다. 

데이터 간의 순서가 있다.

리스트에는 데이터 삽입, 데이터 삭제, 리스트 데이터 탐색하기 3가지의 중요한 연산이 있다.

 

List
ArrayList	LinkedList
	single Linked List	Double Linked List

 

ArrayList (리스트 - 배열)

 

배열 기반의 리스트

메모리 공간을 연속적으로 사용

추가 -> .add

삭제 -> .remove

탐색 -> .get(인덱스 번호)

 

ArrayList 삽입

배열은 선언하면 선언된 크기의 공간을 할당 받는다.

배열의 값이 찬 배열에서 중간의 값을 삽입하기 위해선 삽입 하려는 인덱스의 뒷쪽 인덱스들을 모두 오른쪽으로 한칸씩 먼저 이동시켜 주어야한다.

 

옮겨줄 데이터가 1개라면 1번 n개 라면 n번 이동시켜줘야한다. 위는 2개 데이터를 이동시키므로 2번 이동 시키게 된다.

따라서 시간 복잡도는 O(N)이 된다.

 

 

ArrayList삭제

 

삭제했을 때도 N개의 데이터당 N번 이동시키기 때문에 O(N)의 시간 복잡도를 가지게 된다.

 

 

 

ArrayList 탐색

탐색 by index

데이터의 랜덤 엑세스로 해당 위치에 다이렉트로 접근하기 때문 데이터가 아무리 많아도 한번에 해당 위치에 접근해서 데이터를 가져올 수 있기 때문에 시간 복잡도는 O(1)이다.

 

 

---

 

Linked List (리스트 -  연결 리스트)

 

 

 

링크드 리스트는 노드라는 객체로 구성되어 있다. 또한 노드는 데이터를 저장할 수 있는 필드와 다음 노드를 가르키는 넥스트 포인터 필드를 가지게 된다. 노드들이 다 연결된 형태를 링크드 리스트라고 한다.

 

 

 

검색

링크드 리스트는 어레이 리스트와 달리 인덱스를 통한 random access 가 불가능하다.

자신을 가르키는 넥스트 포인터만으로 접근을 할 수 있기 때문에

N개의 노드를 가지고 있는 링크드 리스트의 검색의 시간 복잡도는 O(N)이다.

 

추가 

Tail노드 다음으로 붙는다.

테일 노드까지 찾아가서 뒤에 추가함으로 테일 노드 까지 찾아가는 과정이 걸리므로 시간 복잡도는O(N)을 갖는다.

 

삽입

어레이 리스트와는 다르게 데이터를 한칸씩 다 미룰 필요가 없다. 간단하게 포인터만 수정해주면 삽입이 된다. 이때 삽입하기 위해 해당 노드까지 찾아가는 과정때문에 시간 복잡도는 O(N)이다.

 

삭제

어레이 리스트와 달리 삭제후 뒤 데이터를 모두 한칸씩 다 끌어올 필요는 없다. 삭제해야할 노드까지 찾아가는 과정만이 필요한다.

자신이 갖고 있던 넥스트 포인터 값을 이전 노드의 넥스트 포인터 값으로 할당해주고 자신은 아무 참조 값도 갖고 있지않기 때문에  JAVA의 가비지 콜렉터에서  자동으로 삭제가 이루어진다.

 

링크드 리스트의 장점

1. 배열의 복사(삭제, 삽입경우 배열의 값들이 오른쪽이나 왼쪽으로 하나씩 이동)나 재할당 ( 어레이 리스트 경우 리스트가 꽉차면 크기를 더 늘려주는 과정이 있다.) 없이 데이터 추가 가능 

2. 유연한 공간 ( 어레이 리스트 경우 뒤에 빈 배열이 좀만 남아도 모두 잡고 있지만 링크드 리스트는 쓰는 공간 만큼만 늘어났다, 줄었다 한다.)

 

단점

random access가 안되기 때문에 데이터를 찾아 접근에 대한 시간이 늘어난다. O(N)의 시간이 걸린다.

 

 

LinkedList 와 ArrayList 차이

 

이러한 시간 복잡도 차이 때문에 LinkedList 는 삽입이나 삭제가 많은 경우에 사용하고  ArrayList 는 검색할 경우가 많을 때 사용한다.

 

---