단순, 원형, 이중 연결 리스트 간단정리

단순 연결 리스트

- vector & arrayList

ArrayList 는 Vector를 개선한 것으로 구현원리와 기능이 동일하다.

저장순서가 유지되고 중복을 허용한다.

배열기반으로 데이터를 저장한다.

Vector는 동기, ArrayList는 비동기!

 

- LinkedList

불연속적으로 존재하는 데이터를 연결함.

데이터 삭제는 한 번의 참조 변경,

데이터 추가는 Node 객체를 생성후 한 번의 참조 변경으로 수행할 수 있다.

 

- ArrayList vs LinkedList

순차적으로 데이터를 추가/삭제하는 경우, arraylist가 빠르다.

비순차적으로 데이터를 추가/삭제하는 경우, linkedlist가 빠르다.

접근시간은 ArrayList가 빠르다

why? 인덱스로 데이터를 접근하기 때문에 인덱스만 알고있다면 O(1)이다

 

linkedlist는 추가/삭제해야할 노드를 찾는데 O(N)이기 때문에 어떤 경우에도 O(N)

---

원형 연결 리스트

마지막 노드와 첫번째 노드가 연결되어 이전 노드에 접근 가능하다.

마지막에 노드 삽입 = 첫번쨰에 노드 삽입

---

이중 연결 리스트

노드와 노드가 연결되어있다.

노드 탐색이 양방향으로 가능하다.

prev를 지정해야해서 단순 연결 리스트보다 변수를 더 사용해야한다.

 

데이터 추가

데이터 삭제