50일차 파이썬 CDR 개발 - 10

파이썬으로 CDR 개발을 시작하면서 막히게 되는 부분이 많아졌는데, 다시 C언어를 하면서 생각이 전환될만한 것을 찾아볼까 한다.

문제	단일 연결 리스트의 길이 구하기
설명	노드의 길이를 int 형으로 반환하는 length 함수 만들기

 

단일 연결 리스트의 구조(노드 구조는 struct Node)

head 노드 포인터가 연결리스트의 첫번째 노드를 가리키고 있다.

§ 연결 리스트

• 리스트의 연결 자료구조로 표현

• 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

노드의 논리적 구조

§ 연결 리스트의 노드

• 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조

 

• 데이터 필드 (Data Field)

− 원소의 값을 저장

− 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성

 

• 링크 필드 (Link Field)

− 다음 노드의 주소를 저장

− 포인터 변수를 사용하여 주소값을 저장

 

§ 단순 연결 리스트 (Singly Linked List)의 개념

• 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가짐

 

§ 단순 연결 리스트 (Singly Linked List)에 삽입하는 방법

 

§ 단순 연결 리스트 (Singly Linked List)에서 노드를 삭제하는 방법

§ 단순 연결 리스트 (Singly Linked List)의 알고리즘

• 첫 번째 노드로 삽입하기

➊ new ← getNode();

new ←  getNode ();

➋ new.data ← x;

new.data  ← x ;

➌ new.link ← L;

삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소(L)를 삽입할 새 노드 new의 링크 필드(new.link)에 저장하여, 새 노드 new가 리스트의 첫 번째 노드를 가리키게 한다.

new.link  ← L;

➍ L ← new;

리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에, 새 노드의 주소 new를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정

L ← new ;

§ 포인터 멤버 연산자 ( -> )

• 구조체 포인터를 선언하게 될 경우, 포인터 멤버 연산자를 통해 참조해줘야 한다.

• 구조체 포인터 이름 -> 멤버 이름  = (*구조체 포인터 이름).멤버 이름

 

C