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

네이버 부스트코스에서 '자바로 구현하고 배우는 자료구조'를 수강하고 있는데 아래의 짤처럼 교수님이 설명할 땐 이해가 쏙쏙 되던게 이해가 안가기 시작했다.

 

간단한 코드인데도 봐도봐도 이해가 안가서 오래동안 고민했는데 내가 노드에 이름을 붙이는 바람에 이해를 못했던거였다...ㅠ 지금 이해한 상태이지만 조금만 딴 생각하면 다시 헷갈릴거 같아서 정리하려고 쓰는 글이다.

 

 

시작!

 

우선 동그라미 네모 육각형으로 이루어진 기존의 리스트가 있다고 생각해보자

그리고 head = 동그라미로 head라는 이름을 가진 변수에 동그라미를 저장해준다.

 

쉽게 생각해봤을 때 i = 3 라고 선언해주면 i는 3을 담은 변수이기도 하지만 3이라는 컴퓨상 어딘가에 있는 데이터를 가리키는 포인터이기도 하다. 

 

i = 3, a = 3, k = 3로 여러 변수에 3을 저장해도 이 3은 각각 다른 3이 아니라 같은 3이며 3을 가르키는 변수들 다른 것이기 때문에 head도 변수이지만 동시에 포인터라고 생각해보자

 

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

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

 

 

그러면

이런 형태가 된다.

 

 

여기서

public void addFirst(E obj) {
	Node <E> newNode = new Node<E>(obj);
    
	newNode.next = head;
	head = newNode;
}

이 코드를 차례 차례 이해해보자. 

 

우선 newNode를 선언하였는데 우리는 newNode를 별로 만들어주겠다.

여기서 별은 연결되어진 노드가 아님을 보이기 위해서 연결된 노드끼리는 화살표를 표시해주었다.(사실 화살표는 처음 그림부터 있어야 했는데 다시 그리기 귀찮아서...ㅎㅎ)

 

여기서 newNode.next = head 는 어떻게 동작하게 될까? 우리는 head라는 변수에 (포인터에) 동그라미를 저장해주었으니 newNode.next = 동그라미 라고 위 코드를 이해해 줄 수 있다. 

 

그럼 newNode라는 별 안에 있는 next에 동그라미 노드가 저장되는 것이니 화살표를 붙여줄 수 있게 되었다!

 

갑자기 next가 왜 나오지? 하시는 분들은 아래의 코드를 참조해주시면 된다.

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;
	}
}

다시 본론으로 돌아와서

이렇게 화살표가 생겼다!

 

이제 마지막 코드인 head = newNode를 이해해보자.

 

head는 뭔가? 변수이며 컴퓨터 어딘가에 저장된 데이터를 가르키는 포인터이다. 그렇기에 head라는 변수에 newNode라는 별을 저장하면 head = 어딘가에 있는 별이 되어서 아래의 그림과 같이 변한다.

 

 

연결 리스트를 생각할 때는 '리스트'라는 관점에 사로잡히는거 보다 '컴퓨터 어딘가에 있는 데이터들의 집합'으로 생각해보는게 이해해기 훨씬 수월한거 같다.

 

나는 head가 움직인다, 데이터를 잇는다 라는 생각을 이해하기가 굉장히 힘들었는데 i=3이다로 head를 이해하는 것이 도움이 많이 되었고 글을 읽는 분들에게도 도움이 되었으면 좋겠다,,ㅎㅎ