단일 연결 리스트(Singly Linked List) 3가지 삭제 방법

1. 헤드 삭제하는 방법

temp = head
head = head -> next
free(temp)

2.끝 삭제하는 방법

prev는  마지막 두 번째 노드를 가리키고 prev의 next를 null로 만들고 end는 삭제합니다.

Node end = head;
Node prev = null

while(end->next) {
 prev = end
 end = end->next
}

prev->next = null

free(end)

3. 특정 위치 삭제하는 방법

삭제할 노드 앞의 포인터와 삭제할 노드에 대한 포인터를 찾습니다.

temp = head;
prev = head;
for(int i = 0; i < position; i++) {
    if(i == 0 && position == 1) {
        head = head->next;
        free(temp);
    } else {
        if(i == position - 1 && temp) {
            prev->next = temp->next;
            free(temp);
        } else {
            prev = temp;
            if(prev == null) break;
            temp = temp->next;
        }
    }
}

 

반복문을 사용하여 삭제 구현

public class SinglyLinkedList {
	static Node head;
	
	static class Node {
		int data;
		Node next;
		
		Node(int d) {
			this.data = d;
			this.next = null;
		}		
	}
	
	static void append(int newData) {
		Node newNode = new Node(newData);
		
		if(head == null) {
			head = newNode;
			return;
		}
		
		Node last = head;
		while(last.next != null) last = last.next;
		
		last.next = newNode;
		return;
	}
	
	static void deleteNode(int position) {
		if(head == null) {
			System.out.println("no head");
			return;
		}
		Node temp = head;
		Node prev = head;
		
		if(position == 1) head = head.next;
		else {
			for(int i = 0; i < position; i++) {
				if(temp == null) {
					System.out.println("no prev");
					return;
				} else if(i == position - 1) {
					prev.next = temp.next;
					return;
				}
				prev = temp;
				temp = temp.next;
			}
		}
			
	}
	
	public static void main(String[] args) {
		append(1);
		append(2);
		append(3);
		deleteNode(2);
		printList(head);
	}
	
	static void printList(Node n) {
		while(n != null) {
			System.out.println(n.data);
			n = n.next;
		}
	}	
}

재귀를 이용한 노드를 삭제 하는 방법

• 노드 포인터를 함수에 매개변수로 전달합니다.
• 참조로 전달되기 때문에 현재 노드가 변경되면 양 옆에 노드도 변경됩니다.
• 주어진 값을 포함하는 노드를 찾습니다.
• 메모리 해제를 사용하려면 해당 노드를 저장합니다.
• 노드 포인터를 변경하여 이전 노드 포인터의 현재 노드 포인터를 연결하도록 합니다.

public class SinglyLinkedList {
	static Node head;
	
	static class Node {
		int data;
		Node next;
		
		Node(int d) {
			this.data = d;
			this.next = null;
		}		
	}
	
	static void append(int newData) {
		Node newNode = new Node(newData);
		
		if(head == null) {
			head = newNode;
			return;
		}
		
		Node last = head;
		while(last.next != null) last = last.next;
		
		last.next = newNode;
		return;
	}
	
	static int deleteNode(Node head, int val) {
		if(head == null) {
			System.out.println("no element");
			return -1;
		}
		
		if(head.data == val) {
			if(head.next != null) {
				head.data = head.next.data;
				head.next = head.next.next;
				return 1;
			} else 
				return 0;
		} 
		
		if(deleteNode(head.next, val) == 0) {
			head.next = null;
			return 1;
		}
		
		return -1;
	}
	
	
	public static void main(String[] args) {
		append(1);
		append(2);
		append(3);
		append(4);
		deleteNode(head, 2);
		printList(head);
	}
	
	static void printList(Node n) {
		while(n != null) {
			System.out.println(n.data);
			n = n.next;
		}
	}	
}

삭제할 노드를 찾으면 그 노드를 다음 노드로 대체해서 삭제하는 방식인데 마지막 노드를 삭제하는 경우 그 이전에 노드에 포인터를 null로 만듭니다.