[Singly Linked List] 검색, 삽입, 삭제

• memo
  • head의 역할
    • 가장 첫 번째의 주소값을 가리킨다.
  • add 메소드에서 if로 인덱스를 검사하는 경우 추가되지 않은 상태에서 size+1이 되었다고 생각하는 것이 맞는지 궁금궁금
• int indexOf(T item)
  • 찾고있는 데이터와 같은 데이터를 가진 노드의 인덱스를 반환 
  • 연결 리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회(traverse)한다고 말한다. indexOf 메소드는 입력된 데이터 ite과 동일한 데이터를 저장한 노드를 찾아 그 노드번호(index)를 반환한다. 그 반환과정을 위해 연결리스트를 순회한다.

	public int indexOf(T item) {	// search
		Node<T> p = head;
		int index = 0;	// index값을 초기화
		while(p != null){	// 다음으로 지정되는 p노드가 없을 때까지 whild문을 반복
			if(p.data.equals(item))	// item이 p노드의 데이터와 같은 경우 해당 index를 리턴
				return index;
			p = p.next;	// 아니라면 다음 노드를 p로 만듦
					// 만약 다음 노드가 없다면 p는 null이 될것이고 다음 while반복에서 중지
			index++;	// index 증가
		}
		return -1;
	}

 

• Node<T> getNode(int index)
  • 연결리스트의 index번째 주소를 반환

	public Node<T> getNode(int index){
		if(index < 0 || index >= size)	// 입력된 인덱스의 유효성 검사
			return null;
		Node<T> p = head;	// 처음 노드(head)를 p에 할당
		for(int i = 0; i < index; i++)	// 입력받은 인덱스 전 노드까지 전진시키기
			p = p.next;	// 현재 p의 다음노드의 p주소값을 받아 p에 저장
		return p;
	}

 

• T get(int index)
  • index번째 노드에 데이터를 반환

	public T get(int index) {
		// 입력받은 index가 유효하지 않고 유효성 검사를 하지 않을 경우 
		//getNode의 반환값이 null이 되고 이는 null.data를 실행하는 결과를 낳게하므로 
		// 유효성 검사를 해주어야 한다. 
		if(index < 0 || index >= size)	
			return null;	

		return getNode(index).data;
	}

 

• void add(int index, T item)
  • 연결리스트의 index번째 위치에 새로운 데이터를 삽입

	public void add(int index, T item) {	//insert
		if(index < 0 || index > size)	// 인덱스를 넘어서는 범위인경우 처리해주는게 좋지만 일단은 return으로 처리
			return;
		
		if (index == 0)
			addFirst(item);
		else {
			Node<T> q = getNode(index-1);	
			// index번째 노드에 노드를 추가시키고 싶다면 index-1번째 노드 뒤에 추가시켜주면 된다.
			addAfter(q, item);
		}
			
	}

 

• T remove(int index)
  • index번째 노드를 삭제하고 그 노드에 저장된 데이터를 반환

	public void add(int index, T item) {	//insert
		// index > size가 된 이유는 size+1된 곳에 추가하고 싶은경우 
		// index의 크기도 size와 같은 경우가 있을 것이므로 size까지 포함한다.
		// 인덱스를 넘어서는 범위인경우 처리해주는게 좋지만 일단은 return으로 처리
		if(index < 0 || index > size)	
			return;
		
		if (index == 0)
			addFirst(item);
		else {
			Node<T> q = getNode(index-1);	
			// index번째 노드에 노드를 추가시키고 싶다면 index-1번째 노드 뒤에 추가시켜주면 된다.
			addAfter(q, item);
		}
	}

 

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