연결 리스트 - 소개

Back to the Basic!

요즘 다시 자료구조를 공부하고 있다. (왜 인지는 비밀!)

윤성우의 "열혈 자료구조" 책을 다시 보고 있는데, 진짜 좋다!

윤성우님을 만나본 적은 없지만 존경하고, 속으로 굉장히 감사하고 있다.

내가 이 책을 조금 더 일찍 만났더라면.. 자료구조 성적을 더 잘 받을 수 있지 않았을까 라는 생각을 하게된다.

 

오늘 소개할 내용은 자료구조 중 연결 리스트이다.

자료 구조에 대해 잠깐 소개하자면 - 자료를 효과적으로 저장하기 위한 방식에 관한 내용이다.

생각해보자! 컴퓨터에는 엄청난, 수많은 데이터들이 저장된다.

이를 잘 활용하기 위해서는 데이터를 잘 저장해서 원할 때 빨리 찾을 수 있어야 한다. 

-> 그래서 수 많은 정렬 알고리즘이 등장한다. 데이터를 알파벳 순서대로 정렬하던지, 정리를 해 놓아야 빨리 찾을 수 있으니까!

또한, 메모리가 무한정인 것이 아니기 때문에 쑤셔넣지 않고 차곡 차곡 잘 저장해야 한다. 

줄줄이 사탕

연결리스트란, 말 그대로 데이터를 연결된 리스트 형태로 저장하는 것을 의미한다. 

줄줄이 사탕을 생각하면 된다. 

한 데이터 뒤에 다음 데이터가 오고, 또 그 뒤에 다음 데이터가 오고!

누구나 상상할 수 있는 그런 방식이다. 

줄줄이 사탕처럼 생긴 연결리스트

이러한 형태의 자료 구조를 쉽게 구현할 수 있는 방법 중 하나가, 배열로 연결 리스트를 구현하는 것이다. 

언어는 C를 사용하겠다. 

연결리스트라는 자료 구조를 구현하려면 뭐부터 시작해야할까?

우선 연결리스트의 틀 부터 만들어야 한다!

붕어빵을 만들려면, 붕어빵 틀을 만들고 찍어내야 하듯이 

연결리스트를 만들려면 연결리스트 틀을 우선 만들어야 한다.

연결리스트라는 틀에는 어떠한 요소가 필요할까? 

연결리스트 선언을 보기 전에 잠시 생각해 보기 바란다. 

....................(생각할 시간)..................

우선 배열 선언이 필요하겠다!! 

배열이라는 그릇에 각각의 데이터를 담을 것이기 때문에 필요하다. 

그다음에는? 

현재 저장된 값들 중 어디를 가리키는지 알려주는 변수가 하나 필요하다.

이 변수를 이용하여 데이터에 접근을 할 수가 있다. 

마지막으로는 현재 리스트에 몇 개의 데이터가 저장되어있는지 알려주는 변수가 하나 필요하다.

있으면 굉장히 유용한 이유가.. 맨 마지막에 있는 데이터를 참고하기도 편리하고, 몇 개 있는지 알기도 편하다. 

 그래서 이를 코드로 표현하면 다음과 같다.

이제 ArrayList 라는 연결리스트 틀을 만든 것이다.

근데 이름이 너무 길다. -_- (매번 ArrayList라고 정의하기 넘나 귀차늠)

그래서 이름을 "List"라고 다시 정의하겠다. 

그럼 다음 포스트에서는 연결리스트의 구현에 대해 조금 더 본격적으로 알아보겠돠..