[Java] 자바로 구현한 연결리스트(single linkedlist) addLast 메소드 쉽게 이해하는 법

먼저 연결리스트를 구현해준다.

public class LinkedList<E> implements ListI<E>{
	class Node<E> {
		data;
		Node<E> next;

		public Node(E obj) {
			data = obj;
			next = null;
		}
	}

	private Node<E> head;
	private int currentSize;
	
	public LinkedList() {
		head = null;
		currentSize = 0;
	}
}

 

그럼 이제 addLast메소드를 한 줄 한 줄 이해해보자.

public void addLast(E obj) {

	Node<E> tmp = head;
    
	while(tmp.next != null) {
		tmp = tmp.next;
	}
    
	tmp.next = newNode;

}

 

코드를 이해하기 전 사각형, 동그라미, 육각형으로 이루어진 연결 리스트가 이미 존재한다고 가정해보자. 

이때 head는 Node를 저장할 수 있는 변수이며 동시에 포인터라고 이해할 수 있다.

 

i = 3의 i는 3을 저장하고 있는 변수이기도 하지만 컴퓨터 어딘가에 있는 3이라는 데이터를 가리키는 포인터이기도 하다! 왜냐?

 

i=3, k=3, a=3 모두 같은 3이라는 데이터를 가르키는 변수이기 때문이다! 그러니 head도 변수이며 포인터라고 이해할 수 있다.

 

(이해를 돕기 위해 i=3이 포인터라고 했지만 i는 사실 포인터가 아니다.. 자바는 저장하는 값이 클래스인 경우에만 call by value가 아닌 call by refernece인 포인터로 작용한다.. 여기서 노드는 클래스이기에 head는 포인터일 수 있는 것이다...ㅠ)

이해 안가시는 분은 이쪽으로 => 연결 리스트를 공부하고 있는데 포인터라는 말이 계속 나온다 (tistory.com)

 

그러니 지금의 상태는 head = 사각형 이라고 할 수 있다. head는 컴퓨터 어딘가에 있는 사각형이라는 데이터를 가르키는 포인터이자 사각형을 저장하고 있는 변수이다.

 

 

 

여기서 우리는 addLast 메소드를 위해 tmp라는 node를 저장하는 변수이자 포인터를 새로 만들어준다. 

 

(addLast는 새로운 노드를 연결리스트 맨 나중에 연결하는 메소드인데 제일 앞을 가르키는 head를 활용할 경우 효율적이지 않기에 맨 뒤를 가르키는 tmp를 만들고 이를 이용해주는 방식을 활용한다.)

 

Node<E> tmp = head

tmp 라는 노드를 저장하는 변수를 만들고 여기에 head가 갖고 있는 노드를 저장해준다. 우리는 위에서 head = 사각형이라는 것을 확인했기에 tmp = 사각형 임을 이해할 수 있다.

이제 while(tmp.next != null) {tmp = tmp.next} 를 이해해보자. 이 코드는 tmp라는 변수가 연결리스트 제일 나중에 있는 노드를 저장하게끔 하는 코드이다. 

 

tmp = 사각형 일 때 tmp.next = 동그라미이며

tmp = 동그라미 일 때 tmp.next = 육각형이며

tmp = 육각형 일 때 tmp.next = null 이다.

 

그 다음 코드로 넘어가기 전 이해를 쉽게하기 위해선 여기서 노드가 포인터라는 것을 이해해야 한다ㅠㅠ 위에서 말했듯이 자바는 클래스가 전달될때 포인터와 같이 작용된다.

 

이걸 이해하지 않으면 그 다음 코드인 tmp.next = newNode를 이해할 수 없다.

 

우선 설명부터 하자면 tmp.next에 newNode(별)이 저장되기에



이런 형태가 된다. 그런데 문제는 여기서부터 시작된다.

 

tmp.next = newNode라는 코드가 실행되고 나면 tmp는 어떻게 될까?

 

정답 : addLast 메소드가 끝나며 tmp는 가비지 컬렉터에 의해 사라진다. 

 

 

나는 이걸 이해하기가 너무 어려웠다. 그림으로만 보면 tmp는 멀쩡히 리스트에 연결되어 있는데 tmp만 사라지고 리스트는 사각형-원-육각형-별의 형태를 유지한다고 한다.......ㅇ{ㅖ??!?

 

우선 tmp는 addLast라는 메소드 안에서 선언된 변수이기에 메소드가 끝나면 가비지 컬렉터에 의해 사라진다.

 

그런데 newNode라는 별은 사라지지 않는데 tmp = 육각형 으로 설명했지만 tmp는 포인터이기도 하기에 포인터에 저장하는 값은 포인터가 가르키는 값에도 똑같이 적용이 된다.

 

newNode는 별이기도 하지만 addLast라는 메소드 밖에서 선언된 노드라는 변수 타입의 일종이기도 하기에 tmp는 사라지지만 tmp.next = 육각형.next 이기도 해서 육각형.next와 연결된 newNode(별)은 사라지지 않는다.

 

즉 tmp.next에 newNode를 저장할때

 

tmp = 육각형 이기에

tmp.next = 육각형.next

tmp.next (=육각형.next) = 별

육각형.next = 별 로 

 

tmp.next에 별이 저장될 뿐만 아니라 동시에 육각형.next에도 newNode가 저장된다.

 

그리고 메소드 안에서 선언된 변수인 tmp는 사라지지만 메소드 밖에서 선언된 노드 중 육각형이라는 변수는 사라지지 않기에 노드와 연결된 별이라는 노드도 사라지지 않는다.

 

 

-끝-

 

최대한 이해하기 쉽게 작성해보았는데 더 어려워지진 않았는지...ㅠㅠ 

혹시 잘못된 부분이 있다면 언제든지 지적해주세요!