[JAVA] 연결리스트, 노드, 삽입 및 삭제

들어가기에 앞서 노드 할당 과정에 대해서 정확히 알고 있어야 한다. 처음에 제대로 이해도 못한 채 무작정 코드부터 뜯어보아서 그런가 오개념만 잔뜩 적립했다. 

- 자유 공간 리스트에서 노드를 할당할 때는 항상 첫번째 노드를 할당한다. 

1. 리스트(L)의 첫번째 노드(head node)의 주소를 포인터 new에 저장하여 포인터 new가 할당할 노드를 가리킨다. 

나는 처음에 주소를 저장하는 것이 아닌 link값을 저장하는 것으로 잘못 이해했다. link가 아니라 노드 자체의 주소!인 것이다. 이 둘의 차이를 잘 알아야 이러한 자료구조를 보다 효과적으로 이해할 수 있을 것 같은... 

 

2. 포인터 L에 리스트의 두번째 노드의 주소(L.link) 저장 

여기서도 주소라는 단어가 나오는데 앞에서 말한 주소와는 다르다. 지금 말하는 주소는 다음 노드의 주소를 뜻하는 것이고 쉽게 말하면 번지수(주소)가 저장되어있다. 

 

노드 반환 과정도 정리 해보자면,

1. 리스트 L의 첫 번째 노드 주소를 반환할 노드 포인터 temp.link에 저장해서 포인터 temp의 노드가 리스트의 첫번째 노드를 가리키게 한다. 한마디로 temp.link는 리스트 첫 노드의 주소를 말하는 것이다!!!!!!!!!!! 그러면 당연히 temp는 첫 노드를 향하겠지.. 하 드디어 깨달았음...

2. 포인터 temp의 값 즉, 반환할 노드의 주소를 포인터 L에 저장해서 리스트 L의 첫번째 노드로 지정한다. 그러면 위 사진 파란 글씨 부분에서 볼 수 있듯이 포인터 L은 100이라는 주소값을 갖게 된다. 

 

package listNode;

public class ListNode {
	
	private String data;
	ListNode link; //ListNode라는 객체를 참조함. 
	
	public ListNode(){
		this.data = null;
		this.link = null;
	}
	public ListNode(String data){
		this.data = data;
		this.link = null;
	}
	//데이터와 링크 필드를 가리키는 생성자
	public ListNode(String data, ListNode link){
		this.data = data;
		this.link = link;
	} 
	//getter&setter(멤버함수)
	public String getData(){
		return  this.data;
	}
	public void setData(String data) {
		this.data = data;
	}
	public ListNode getLink(){
		return  this.link;
	}
	public void setLink(ListNode link){
		this.link = link;
	}
}

 

1. insertMiddleNode - (1)

public void insertMiddleNode(LinkedList L, ListNode pre, String data){       
		ListNode newNode = new ListNode(data); 
		if (L.head == null) {
			L.head = newNode;
			newNode.link = null;
		}
		else { 
			newNode.link = pre.link;
			pre.link = newNode;
		}
	}

[인수 : 새로운 연결리스트 L, 삽입할 노드 이전 원소 pre, data값]

ListNode newNode = new ListNode(data); //data = data, link = null값인 새로운 삽입할 노드 생성

기존 연결리스트에 원소가 없을 경우 리스트의 삽입 노드는 삽입되는 노드이자 동시에 head node이자, 마지막 tail node이기도 하다. 따라서 link값을 null으로 지정해주었다. 

이와 같은 경우를 제외하고는 새로운 노드의 link는 이전 link값을 참조하게되고 결국 현재의 포인터 값의 pre 노드가 된다. 

 

2.insertLastNode - (2)

public void insertLastNode(String data){
		ListNode newNode = new ListNode(data);
		if(head == null){
			this.head = newNode;
		}
		else{
			ListNode temp = head;
			while(temp.link != null) temp = temp.link;
			temp.link = newNode;
		}
	}

[인수 : 새로운 노드의 data값]

head == null인 경우는 쉬우니까 패스.

null이 아닌 경우에는 현재 리스트 L의 마지막 노드를 찾기 위해 노드를 순회할 임시 포인터 temp에 L의 head 노드의 주소를 지정한다. while 반복문을 돌면서 temp가 노드의 링크 필드를 따라 이동한다. link가 null이면 마지막 노드를 찾는 데 성공하고 while문 종료한다. temp가 가리키는 노드 즉, 리스트의 마지막 노드의 link field에 삽입할 newNode 주소를 저장하여 마지막 노드가 새 노드 newNode를 연결한다. 

 

3. deleteLastNode

public void deleteLastNode(){ 
			ListNode pre, temp; 
			if(head == null) return; 
			if(head.link == null) {
				head = null;
			}
			else {
				pre = head;
				temp = head.link;   
				while(temp.link != null) { 
					pre = temp; 
					temp = temp.link;
				}
				pre.link = null;
			}
	}

[인수 : X]

***포인터 temp가 차례대로 다음 노드를 가리키면서 진행되는 알고리즘인데 나는 전혀 다르게 이해했다.. 첫번째 if는 빈 리스트인 경우, 두번째 if는 원소가 하나인 경우, 그리고 마지막은 그 외의 경우로 말이다. 그래서인지 이해가 전혀 안되었다. 이래서 오개념이 무서운거지...ㅜㅜ 

노드 pre의 다음 주소를 포인터 temp에 저장하여 포인터 temp가 다음 노드를 가리키게 한다. 만약 노드 pre가 리스트의 마지막 노드였다면? pre.link = null = 포인터 temp값 이 된다. 결국 다음에 삭제할 노드가 없다는 뜻으로 삭제연산 수행하지 못하고 return.삭제할 노드의 다음 노드를 pre.link로 연결한다. pre.link = null 로 삭제한 노드를 자유 공간리스트에 반환한다. 

 

4. searchNode

public ListNode searchNode(String data){
		ListNode temp = this.head;
		while(temp!=null){
			if(data == temp.getData()) return temp;
			else temp = temp.link;
		}
		return temp; 
	}

리스트의 노드를 처음부터 하나씩 순회하면서 노드의 data field값을 비교하여 일치하는 노드를 찾는 연산이다. 

 

5. reverseList

public void reverseList(){
		ListNode next = head; 
		ListNode current = null;
		ListNode pre = null; 
		while(next != null) { 
			pre = current;
			current = next; 
			next = next.link; 
			current.link = pre; 
		}
		head = current; 
	}