코딩 인터뷰 완전분석 - 단방향 연결리스트

ctci - 3일차

 

단방향 연결리스트

 

구현이 어려운편은 아니지만, 손으로 써보면서 자세히 생각해보지 않으면 쉽게 이해하기 힘들다.

 

package ctcl_LinkedList;
//Basic Linked List
public class BasicLinkedList {
	class Node{
		Node next = null;
		int data;
		public Node(int data){
			this.data = data;
		}
		void appendToTail(int data) {
			Node end = new Node(data);
			Node tmp = this;
			while(tmp.next != null) {
				tmp = tmp.next;
			}
			tmp.next = end;
		}
		Node deleteNode(Node head, int d) {
			Node n = head; // 임시로 사용할 node n에 head를 넣는다.
			if(n.data == d) { //head node의 데이터와 삭제할 데이터가 같을 경우(head를 삭제하려고 하는 경우)
				return head.next; //head node를 변경한다.
			}
			while(n.next != null) { // 탐색 시 null 포인터 확인 필수
				if(n.next.data == d) { //삭제하려는 노드의 prev 노드에 도달한 경우(n은 prev 노드)
					n.next = n.next.next; //prev 노드의 next 포인터를 삭제하려는 노드의 next 포인터로 바꾼다.
					return head;//head는 변경되지 않음.
				}
				n = n.next; //삭제하려는 노드에 도달하기 위해 조건문에 해당하지 않는 경우 다음 노드로 이동
			}
			return head;//삭제하려는 노드를 찾지 못한경우, head를 변경하지 않은 상태로 끝남.
		}
	}
	public static void main(String [] args) {
		BasicLinkedList b = new BasicLinkedList();
		BasicLinkedList.Node head = b.new Node(3);
	}
	
}

 

appendToTail 메소드나, Node의 생성자는 직관적으로 이해하기 쉽다.

deleteNode 메소드가 이해가 필요한데, 인수로는 연결리스트의 head node와 삭제할 데이터가 있다.

가장 중요한 점은 두가지로,

1. 노드 내 탐색시에 null 포인터 검사를 꼭 해주어야 한다.

2. 필요하다면 head나 tail 포인터도 갱신해야한다.

첫번째 조건의 이유는 null 포인터 검사를 하지 않으면 당연히 노드의 끝까지 가고도 찾지 못한 경우 null 포인터 참조 오류가 나기 때문이다.

두번째 조건의 이유는, head나 tail 포인터를 삭제하려고 한다면, head나 tail을 삭제하기 전에 head나 tail을 필수적으로 변경해주어야 단방향 연결리스트가 유지되기 때문이다.

 

 

추가적인 사항

해당 코드를 작성 할 때, 외부 클래스와 내부 클래스로 나누어서 코딩했기 때문에, main에 보면

Outer class : BasicLinkedList

Inner class : Node

 

main에서 선언시

Outer outer = new Outer();

Outer.Inner inner = outer.new Inner();와 같은 형태로 사용해야한다.

 

먼저 BasicLinkedList b = new BasicLinkedList();를 실행하게 되면

이너 클래스 인스턴스를 포함한 외부 클래스 인스턴스가 코드 섹션에 올라오게되고,

 

BasicLinkedList.Node head = b.new Node(3);을 실행 할 경우에 Innter 클래스의 인스턴스가 생성되게된다.

 

이번에는 연결리스트보다 Java 클래스 공부를 더한.. 느낌.