자료구조 7일차 : 연결리스트

오늘은 지난 시간에 살펴본 배열리스트에 이어서 연결리스트에 대해 알아보겠습니다.

연결리스트는 주소(포인터)를 이용하여 리스트를 구현한 자료구조들 중에 하나입니다.

 

 

연결리스트 또한 주소(포인터)를 이용해서 노드끼리 연결합니다.

 

연결리스트를 구현하기 위해서는 우선 노드의 구조를 생각하여 구조체로 선언해야합니다.

위의 그림과 같은 구조를 가질 수 있도록 노드 안에 데이터를 담을 공간과

링크를 선언해 구조체를 만들어줍니다.

 

 

배열리스트와 연결리스트의 차이점 입니다.

연결리스트는 스택, 큐와 다르게 헤더노드라는 것이 존재합니다.

 

헤더노드는 실제 자료를 저장하는 노드가 아니라 다음 노드에 대한 링크(주소)를 저장하는 노드를 뜻합니다.

자료를 저장하지 않음으로 노드의 개수에 포함시키지 않습니다.

헤더노드는 앞으로 들어올 데이터에 대해서 기준을 잡아주는 역할을 한다고 생각하시면 될 것 같습니다.

 

헤너노드의 선언과 헤더노드를 그림으로 표현한 그림 입니다.

헤더노드는 들어오는 데이터와 연결되지만 노드의 개수로는 포함시키지 않습니다.

 

노드 구조체를 생성한 뒤에 연결리스트를 생성하기 위해

createList() 연산자를 선언한 뒤 정의를 내려주겠습니다.

헤더노드의 포인터 변수를 선언한 뒤 동적할당을 해줍니다.

그 뒤에 초기화를 해주고 pReturn을 반환시켜줍니다.

 

그 다음으로는 연결리스트에서 특정 값을 가져오는 연산자를 만들어주겠습니다.

특정 데이터를 가져오는 getLinkedListData 연산자와 그에 대한 알고리즘입니다.

position 번째 인덱스의 데이터를 가져오는 연산자입니다.

알고리즘과 함께 해석을 해보시면 이해하기 쉬우실 겁니다.