1. 리스트(3) List Iterator, DLink

• List Iterator와 Doubly Linked List(이하 DLink)는 왜 등장하게 되었을까?
  Array List와 Linked List의 리스트 순회 시간 복잡도는 어떻게 될까?

List<Integer> list = new ArrayList<>(); (혹은 new LinkedList<>();)

for(int i = 0; i < list.length(); i++)
	System.out.println(list.getValue()); // 리스트 순회하는 이 구문의 시간 복잡도는?

        Array List의 경우 : O(n)

        Linked List의 경우 : O(n²)

• Linked List의 시간 복잡도를 줄일 수 있는 방법이 뭐가 있을까?
  첫번째 방법 - curr을 매번 이동하는 것이 아닌 한 노드 옮겨갈 때마다 그 위치를 기억하도록 하자.

Link<Integer> curr = (LinkedList<Integer> list).head(); //Linked List로 형변환(Type cast)
Link<Integer> tail = (LinkedList<Integer> list).tail();

while(curr != tail){ // curr이 tail이 되기 전까지 하나씩 앞으로 전진하는 방식
	curr = curr.next();
    System.out.println(curr.item());
}

        해당 방법을 사용하면 Linked List의 시간 복잡도는 O(n)이 된다.
        

        문제점 - 그렇다면 ADT는 왜 만들었고, 코드가 간결해지지 못한 모습이다. 또한 리스트로서 사용하고 싶을 뿐인데 Linked List로 형

        변환까지 해야한다면 굳이 이 코드를 사용할 의미가 있는가?


        두번째 방법 - Iterator 패턴을 사용하자!

• Iterator Pattern

List Iterator ADT

public interface Iterator<E>{
    boolean hasNext(); // curr의 다음이 있는가?
    E next(); // 다음 값을 가져와준다.
    boolean hasPrev(); // curr의 이전이 있는가?
    E prev(); // 이전 값을 가져와준다.
}

• Array List의 경우(구현)

• Linked List의 경우(구현)

• List Iterator의 한계
  반대 방향 순회 previous()의 시간 복잡도가 여전히 O(n²)이다.
  해결책 : DLink
• Doubly Linked List(이하 DLink)
  DLink란? next와 prev를 모두 가지고 있는 노드들이 연결된 리스트

        구현

        Insert 와 Remove