[Singly Linked List] node 추가하기

• memo
  
  • 내가 작성한 코드가 일반적인 경우뿐만 아니라 특수한 혹은 극단적인 경우에도 문제 없이 작동하는지 철저하게 확인하여야 한다.
    • 추가시키는 노드의 다음 노드가 없는경우
    • 삭제하려는 노드의 다음 노드가 없는경우 등등
• Node
  
  • 구성
    • 데이터 필드
    • 링크 필드
      
      • 다음 node의 주소를 참조함
      • 첫 번째 node의 주소는 따로 저장하여야 함

linkedlist 구조

• LinkedList에 새 노드 추가시키기(처음 노드로)
  • addFirst("Ann")
    1. 새 노드 만들고 추가할 데이터를 저장
    2. 새 노드의 next 필드가 현재의 head노드를 가리키도록 함
       
       • newNode.next = head
    3. 새 노드를 새 head 노드로 함
       • head = newNode
  • 순서가 중요
    • 추가하기전의 head의 값은 기존에 있던 가장 처음 노드의 주소값과 같으므로 새로운 노드의 주소값을 먼저 head에 넣어버리면 기존 첫번째 노드의 주소값은 증발하므로 반드시 먼저 head에 있는 기존 노드의 주소값을 가져와서 새 노드의 링크필드에 넣어주고 그 다음에 head에 새 노드의 주소값을 넣어준다.
    • 정리: 새 노드의 링크필드에는 기존 첫번째 노드의 주소값이 들어오고 head에는 새 노드의 주소값 들어간다.
    • head -> 새 노드 -> 기존 첫번째 노드
  • addFirst 할 때 연결리스트에 노드가 하나도 없다면?
    • head = null인 상태 
    • 2번 과정
      • newNode.next = null
    • 3번 과정
      • head = newNode(새 노드의 링크필드)
    • head -> newNode의 data: "Ann", next: null
• Node.java

public class Node<T> {
	public T data;
	public Node<T> next;
	
	public Node( T item ) {
		data = item;
		next = null;
	}
}

• MySingleLinkedList.java

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	
	public void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);	// T : type parameter, OK
		
		newNode.next = head;
		head = newNode;
		size++;
		
		// not ok
		/*Node<T> []arr = new Node<T> [100];	
		T t = new T();	
		T []array = new T[100];
		*/
	}
	
	public void add(int index, T item) {	//insert
		
	}
	
	public void remove(int index) {		// delete
		
	}
	
	public T get(int index) {
		return null;
	}
	
	public int indexOf(T item) {		// search
		return -1;
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MySingleLinkedList<String> list = new MySingleLinkedList<String>();
		list.add(0, "Saturday");
		list.add(1, "Friday");
		list.add(0,  "Monday");		// M, S, F
		list.add(2,  "Tuesday");	// M, S, T, F
		
		String str = list.get(2);	// str = "Tuesday";
		list.remove(2);	// M, S, F
		int pos = list.indexOf("Friday");	// pos = 2;
	}

}

출처:

인프런 java로 배우는 자료구조

4-2장: 연결리스트의 개념과 기본연산2

https://www.inflearn.com/course/java-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0