[Singly Linked List] node 삽입, 삭제

• addAfter(Node<T> before, T item)
  • 만들고자 하는 구조
    • before노드 > new 노드 > 다음 노드
  • 순서
    1.  new 노드를 만들고 데이터를 저장
    2.  new 노드의 next필드가 다음 노드를 가르키도록 함
    3.  before 노드의 next필드가 new노드를 가르키도록 함

	public void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);
		temp.next = before.next;
		before.next = temp;
		size++;
	}

 

• addBefore(Node<T> p, T item)
  • 만들고자 하는 구조
    • new 노드 > p 노드 > 다음 노드
    • 이 경우 간단하지 않다.
      • 이유는 LinkedList 의 노드들은 자신의 다음 노드의 주소값을 가지고 있지 전 노드의 주소값을 가지고 있지 않기 때문
        • temp.next = p
        • 직전 노드.next = temp
        • 직전노드의 주소를 알 수 없기 때문에 직전노드의 next에 temp값을 넣어주기 어렵다.
      • 따라서 어떤 노드 뒤에 노드를 삽입하는 것은 간단하지만 반대로 어떤 노드의 앞에 삽입하는 것은 간단하지 않음
• removeFirst()
  • 만들고자 하는 구조
    • head > 삭제할 노드 > 다음 노드 인 구조가
      head > 다음 노드 가 되도록 연결리스트의 첫번째 노드를 삭제함
  • 삭제할 노드의 데이터를 리턴해줌(리턴해주지 않아도 됨)
  • 순서
    
    1. head다음이 null인 경우 즉, 노드가 하나도 없는 경우에는 return(종료)
    2. head 노드에 다음 노드의 주소를 넣어줌

	public T removeFirst() {
		if(head == null)
			return null;
		T temp = head.data;
		head = head.next;
		size--;
		return temp;
	}

 

• removeAfter(Node<T> before)
  • 만들고자 하는 구조
    • before 노드 > 삭제할 노드 > 다음 노드인 구조가
      before 노드 > 다음 노드 가 되도록 함
  • 삭제할 노드의 데이터를 리턴, 마찬가지로 자유임
  • 순서
    1. before 의 다음이 null인 경우 return(종료)
    2. before 노드의 next에 다음 노드의 주소를 넣어줌
       • before 노드 > 삭제할 노드 > 다음 노드이므로 before.next.next로 표현

	public T removeAfter(Node<T> before) {
		if(before.next == null)
			return null;
		T temp = before.next.data;
		before.next = before.next.next;
		return temp;
	}

 

 

 

• 출처
  • 인프런 java로 배우는 자료구조
    • 4-1장: 연결리스트의 개념과 기본연산 3
    • https://www.inflearn.com/course/java-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0