연결리스트의 문제는 가장 기초적인 것으로 연결리스트를 구현할수 있는가? 부터 시작해야합니다.

class Node {
  Node next = null;
  int data;

  public Node(ind d){
    data = d;
  }

  void appendToTail(int d){
    Node end = new Node(d);
    Node n = this;
    while(n.next != null) {
      n = n.next;
    }
    n.next = end;
  }
}

기본 구현은 이러하다. 그리고 면접시 연결리스트에 대한 질문을 받을 때에는, 단방향 연결리스트인지, 양방향 연결리스트인지 확실히 해야한다.

단방향 연결리스트에서의 노드 삭제

연결리스트에서 노드를 삭제하는 연산은 직관적이다. 노드 n이 주어지면, 그 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정한다.
리스트가 양방향 연결 리스트인 경우에는 n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정해야 한다.

유의할점은

1. Null포인터 검사를 반드시해야하고,
2. 필요하다면 head와 tail포인터를 갱신해야 한다는 점이다.

Node deleteNode(Node head, int d){
  Node n = head;

  if(n.data == d) {
    return head.next;
    // head가 변경됨.
  }

  while(n.next != null) {
    if (n.next.data == d) {
      n.next = n.next.next;
      return head;
    }
    n = n.next;
  }
  return head;
}

Runner 기법

“Runner”기법은 연결 리스트 문제에서 많이 활용 된다. 연결 리스트를 순회할 때 두개의 포인터를 동시에 사용

재귀 문제

재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 필요로 할 것임은 기억하자. 모든 재귀 알고리즘은 반복적인 형태로도 구현될 수 있긴 허지만, 한층 복잡해진다.