data structure

[Singly Linked List] node 삽입, 삭제

tonirr 2020. 3. 14. 16:18
  • 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;
	}