연결 리스트

perl로 연결리스트를 한번 구현해 보자.

연결리스트가 어떤것인지 궁금하다면...

위키디피아의 연결리스트를 보시기 바란다.

http://ko.wikipedia.org/wiki/연결_리스트

그래도 잘 모르겠다는 분들을 위해서 간단히 정리해 보았다.

연결 리스트

- 연쇄적으로 연결된 원소로 이루어진 자료구조



데이터들이 쭉~~~ 연결되어있는 구조를 이야기한다.


지나가던 행인1  :  배열도 쭉~ 연결되어 있잖아?


죄송.. 설명이 시원찮아서......

일단 밑의 그림을 보시라...

위의 그림으로 설명하자면...

데이터( data ) 뒤에 다음 데이터를 가르키는 주소( next )가 담겨져 있다.

다음 데이터를 추가하고 싶을때는 데이터와 다음주소값을 가르키는 값을 하나 더 생성한뒤

이 전의 주소와 연결만 시켜주면 계속적으로 연결된 리스트가 만들어 지는 것이다.



지나가던 행인2 : 어휴.. 데이터만 있으면 되는거지 왜 다음주소로 연결하는것까지 만들고 그래요??


perl로 배우는 알고리즘 왈 : 

큰 배열의 가운데에서 원소를 추가하거나 삭제하는 것이 시간소모가 심하기 때문에

연결리스트를 사용하면 이러한 시간의 소모를 줄일 수 있다.


h0ney 군의 해석 :

10000개의 배열에 각각 데이터들이 모두 들어 있다고 생각해 보자.

만약 첫번째 자료를 지운 뒤 배열이 비어 있으면 곤란하니

뒤에 있는 자료를 모두 앞으로 이동시킨다고 생각해보면...

단지 자료 하나를 삭제하는데...

10000개의 자료를 모두 한칸씩 앞으로 이동을 시켜야 하니... 엄청난 시간이 소요될 것이다.

그렇게 프로그래밍을 짜고 싶은가?

프로그래밍에서 시간은 생명이며 궁극적으로는 돈이다.....  ;ㅁ; ...




컴퓨터계열 대학생들이라면 자료구조론을 다들 접해봤을 것이다... (모르는 사람은 프로그래밍 무지 싫어했....)

허벌나게 C만 하는 우리나라의 특성상

대부분 C로 연결리스트를 구현하였을 것인데...

C언어에서는 구조체 + 포인터 신공으로 연결리스트를 쉽게(?) 구현이 가능하다.



perl에서는 어떻게 연결리스트가 구현이 될지.. 궁금 x 100  하지 않은가?

Go ~ Go!

연결리스트를 만들기 이전에 먼저 두개의 상수를 선언하겠다.

 

use constant NEXT  => 0; 
use constant VAL   => 1;

 

이것은 상수 0 과 1 에 이름을 붙여 코드를 조금 더 읽기좋게 선언한 것이다.

constant를 사용하는데 컴파일때 시간이 조금 더 들지만 실행할 때 속도 저하는 없다.


linked.pl

1 2 3 4 5 6 7 8 9 10

use constant NEXT => 0; use constant VAL => 1; $list = undef; foreach (reverse 1..5){ $list = [$list,$_ * $_]; } for(;$list != undef;$list = $list->[NEXT] ){ print $list->[VAL]."\n"; }

$list 는 처음 undef 로 초기화를 시킨다.


반복시 가장 먼저 5의 제곱인 25라는 값이

무명배열( [ ] )안의 두번째 원소에 저장되며,

처음 원소는 undef였던 $list를 저장한다.

그리고 이것의 레퍼런스를 $list 라는 변수에 다시 저장을 시키는 형식으로 총 5번을 반복한다.


25부터 차례대로 연결이 되기 때문에 결국에는 1이 가장 처음의 원소의 값이 된다.

이해를 돕기위해 그림으로 그려보았다.

출력하는 구문은 for으로 구현하였다.

처음값인 $list가 undef일 때까지 list의 NEXT 값으로 접근하며 그 값을 출력을 하니

간단히 저 2줄의 코드만으로 모든 값의 출력이 가능하다.

Output:

1 2 3 4 5

1 4 9 16 25

http://codepad.org/wHB3YXP5


오늘은 여기까지!

다음편에는 연결리스트를 조금더 고급적으로 사용하는 법에 대해서 기술하겠다.