ArrayList vs LinkedList

ArrayList → 일반적인 배열 형태의 자료구조. 노드의 삽입, 삭제 시 마다 모든 데이터의 위치를 앞 또는 뒤로 옮겨줘야 하므로 효율이 나쁨

LinkedList → 포인터를 통해 노드의 삽입, 삭제 시 다른 포인터 값만 변경해주면 됨

ArrayList

//일반적인 배열 선언과 같음
int[] arr = new int[100];

LinkedList

1. LinkedList 클래스 선언 및 생성

class Node<E>{
  //노드
  E data;  // 인스턴스 data는 제네릭으로 구현
  Node<E> next;  // 포인터

  //생성자
  Node(E data, Node<E> next){  //(노드)생성
    this.data = data;  //data필드 입력
    this.next = next;  //연결된 노드 입력
  }
  
  Node<E> head;  
  //첫번째 노드를 가리키기 위한 헤드 포인터(노드를 탐색할 때 시작하는 위치를 지정)
  Node<E> crnt;  
  //선택한 노드를 가리키기 위한 선택 포인터(crnt 노드가 가리키는 위치의 노드를 삽입및 삭제)

  public LinkedList(){  //리스트 생성
    head = crnt = null;
    //노드 head와 crnt에 null을 저장해서 비어있는 LinkedList생성

• 제네릭이란

2. 검색 메서드 선언

탐색을 하기 위해 가리키는 포인터노드를 선언하고, 포인터노드가 가리키는 노드의 next를 통해 이동하면서 검색

public E search(E obj, Comparator<? super E> c){  //<? super E>:?
  Node<E> ptr = head;  //시작을 head
  while(ptr != null){  //포인터값이 null인 노드가 나올 때까지
    if(c.compare(obj, ptr.data) == 0){  //검색값과 현재노드의 값을 비교
      crnt = ptr;
      return ptr.data;
    }
    ptr = ptr.next;
  }
  return null;
}

• Comparator?
• super?
• Comparator<? super E>

//매개 변수자리인데 왜 comparator<? super E>가 들어가는지