Day06 - jeremy0405/Codesquad_CS GitHub Wiki

LinkedList

• 아이템을 보관하는 노드와 다음 노드를 연결하는 포인터로 연결한 선형 자료구조
• 아이템은 하나 혹은 여러 값을 보관
• 포인터는 다음 노드를 참조

List Operation

// 구현
size()
get(int index)
insert(int index)
delete(int index)
addLast()

// 미구현
isEmpty() -> return size == 0 으로 간단히 구현가능 필요없어보여서 생략
addFirst() -> 굳이 말하자면 insert로 대신 가능

미션을 수행하면서 단일 연결 리스트를 구현했다.

위에서 파란색이 VideoData class의 객체이고 이를 담고 있는 MyLinkedList를 구현했다.

구현방법을 간단히 소개하려고 한다.

1. add(VideoData newData)
   • 먼저 데이터가 아예 없는 경우에는 MyLinkedList의 head 가 newData 를 가르키도록 하면 된다.
   • 데이터가 이미 존재하는 경우 nextNode 가 null 인 지점(마지막지점)까지 가서 nextNode가 newData 를 가르키도록 하면 된다.
2. delete(VideoData newData)
   • delete()를 실행하기 전에 데이터가 MyLinkedList에 있는지 검증 후에 실행하도록 전처리를 했다.
   • id를 비교해서 동일한 id가 나오면 그 데이터를 삭제했다.
     • 데이터가 0번째 index에 있는 경우에는 head를 0번째 노드의 nextNode와 일치시켰다.
     • 데이터가 0번째 index가 아닌 경우에는 (index - 1) 노드의 nextNode를 index의 nextNode로 변경해주었다.
3. insert(VideoData newData, int index)
   • 데이터를 0번째 index에 insert하려는 경우에는 newData의 nextNode를 head와 일치시킨 후 head를 newData로 변경하였다.
   • 데이터를 0번째가 아닌 index에 insert하려는 경우에는 (index - 1) 노드의 nextNode를 newData의 nextNode에 대입한 후 (index - 1)의 nextNode를 newData를 가르키도록 했다. insert 시 순서가 매우 중요하다

public void insert(VideoData newData, int index) {
	if (index == 0) {
		newData.setNextNode(this.head);
		this.head = newData;
	} else {
		// (index - 1) 노드의 nextNode를 newData의 nextNode에 대입
		newData.setNextNode(get(index - 1).getNextNode());
		// (index - 1) 노드의 nextNode에 newData를 대입
		get(index - 1).setNextNode(newData);
	}
}

4. get(int index)
   • 단순히 index 만큼 for문을 통해서 nextNode를 찾아가서 index에 있는 노드를 반환했다.
5. size()
   • add 또는 insert 시에는 size++, delete 시에는 size-- 를 통해 전역변수로 size를 관리하고 있었다. 이를 바로 반환해주었다.

insert시 노드의 참조(nextNode)를 연산하는 순서가 중요한 이유

위의 3번의 insert 순서로 한 경우

참조를 바꾸는 순서를 3번의 insert와 반대로 한 경우

순서를 바꾸면 위와 같이 길을 잃게 된다. 이후에 참조되지 않은 모든 자료를 GC에 의해 잃게 될 수도 있다. 이를 방지하고자 tmp 값을 통해서 임시로 (index - 1)의 nextNode값을 저장할 수도 있지만 코드의 양을 늘리고 메모리를 더 사용할 필요는 없다.