linkedList 노드의 추가와 삭제

likedList 노드의 추가와 삭제

---

0. linkedList 생성

 MyLinkedList 클래스

public class MyLinkedList {
	private MyListNode head;
	int count;
public MyLinkedList() {
	head = null;
	count = 0;		
}

public MyListNode addElement(String data) {
	MyListNode newNode;
	
	if (head == null) {
		newNode = new MyListNode(data);
		head = newNode;
	}
	else {
		newNode = new MyListNode(data);
		MyListNode temp = head;			
		while(temp.next != null)
			temp = temp.next;		//temp를 MyListNode로 생성했기 때문에 next 받아올 수 있음
		temp.next = newNode;
	}
	count++;
	return newNode;
	}

MyListNode 클래스

public class MyListNode {

	private String data;		//자료
	public MyListNode next;	//다음 노드를 가리키는 링크. 링크는 자기자신의 타입을 가리킴

	public MyListNode() {	 	//링크 X , 자료값 X
		data = null;
		next = null;
	}
	
	public MyListNode(String data) {	// 링크 X, 자료값1 추가
		this.data = data;
		this.next = null;
		
	}
	public MyListNode(String data, MyListNode link) {	//링크 O , 자료값2 추가
		this.data = data;
		this.next = link;
	}
	
	public String getData(){
		return data;
	}
}

// 링크드 리스트를 새로 생성하고 메인에서 add.Element를 사용하여 노드 추가

MyLinkedList list = new MyLinkedList();

---

1. 노드의 추가

   1) 링크의 맨 앞에 추가하기

MyListNode tempNode = head;
MyListNode newNode = new MyListNode(data);
//새 노드를 생성하여 원하는 데이터값을 넣어줌

newNode.next = head;
head = newNode;

 - newNode가 현재 head를 가리키도록 newNode.next 에 head를 넣어줌 ( 현재 head는 링크의 2번째 순서가 됨)

 - newNode를 head로 할당해줌 

---

  2) 링크의 중간에 추가하기 (p번째 자리에 넣기)

MyListNode preNode = null;
		for (int i=0; i <p; i++) {
			preNode = tempNode;
			tempNode = tempNode.next;
		}

 - 최종적으로 preNode는 p-1번째 값이 들어가고, 
    tempNode에는 p번째 값을 가리키는 tempNode.next가 들어감

preNode가 p-1번째 노드, tempNode가 p번째 노드가 됨 (p-1번째, p번째 값을 각각의 노드에 넣어준 것)

newNode.next = preNode.next;
preNode.next = newNode;

 - newNode가 p번째 값을 카리키도록 newNode.next에 preNode.next(p번째 값을 가리킴)를 넣음
 - preNode가 newNode를 가리키도록 preNode.next에 newNode의 주소값을 넣어줌
  ===> p번째 자리에 newNode가 오게 됨

newNode.next가 tempNode를 가리키도록 변경, p번째 tempNode를 가리키고 있던 preNode.next를 newNode를 가리키도록 변경

---

3) 전체 코드

public MyListNode insertElement(int position, String data) {
		int i;
		MyListNode tempNode = head;
		MyListNode newNode = new MyListNode(data);
		
		if (position <0 || position > count) { //유효성 검정
			System.out.println("추가할 위치 오류입니다. 
           					 현재 리스트의 개수는 " +count + "개 입니다." );
			return null;
		}
		if (position == 0){
			newNode.next = head;			   // 추가하고자 하는 위치가 맨 앞일 경우
			head = newNode;
		}
		else {
			MyListNode preNode = null;
			for (i=0; i <position; i++) {
				preNode = tempNode;
				tempNode = tempNode.next;
			}
			newNode.next = preNode.next;
			preNode.next = newNode;
		}
		count++;
		return newNode; 
	}

---

2. 노드의 삭제

 1) 노드의 삭제

MyListNode preNode = null;
for(i = 0; i < position ; i++) {
	preNode = tempNode;
	tempNode = tempNode.next;

 - 최종적으로 preNode에 p-1번째 값,
   tempNode에는 p번째 값을 가리키는 tempNode.next가 들어감

preNode.next = tempNode.next;

 -  p-1번째인 preNode에 p+1번째 값을 가리키는 tempNode.next를 넣음
    최종적으로 p번째 노드는 링크에서 빠지고 GarbageCollector가 삭제하게 됨

---

2) 전체 코드

public MyListNode removeElement(int position ) {
	int i;
	MyListNode tempNode = head;
	if (position >= count ) {
	System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " +count+"개 입니다.");
		return null;
	}
	if (position == 0) {
		head = tempNode.next;	//0번(head)이 삭제되어 head가 다음 주소의 노드가 할당됨
	}
	else {
		MyListNode preNode = null;
		for(i = 0; i < position ; i++) {
			preNode = tempNode;
			tempNode = tempNode.next;
		}
		preNode.next = tempNode.next;
	}
	count--;
	System.out.println(position + "번째 항목이 삭제되었습니다.");	
	return tempNode;
}