포인터를 이용해서 연결리스트 구현하기

연결리스트란

각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로

데이터를 저장하는 자료 구조를 말한다.

*각각의 데이터와 포인터를 가지고 있는 것을 노드라함

*노드의 포인터가 다음이나 이전의 노드들과 연결을 담당함

(마치 기차 처럼 한줄로 이어질수 있게 하는 것)

<전체 코드>

<구현하기>

일단 연결리스트를 만들기 위해서는

노드가 필요하고 노드안에 들어갈 데이터와 각 노드를 연결 시킬 포인터가 필요하다.

int value는 데이터의 값을 넣기 위해 만들었고

Data *pNext는 포인터를 의미한다.

이걸 그림으로 그려보면

 

이런식으로 그릴수 있다.

네모난 상자 하나가 노드를 의미하고 빨간 부분이 데이터가 들어가는곳

화살표가 포인터를 의미한다.

이런식으로 데이터를 저장하는 것을 연결리스트라고 한다.

마지막 노드에 /은 NULL이라는 의미로 다음 데이터가 존재 하지 않는다는 것을 말하는 것이다.

그리고 Data *head는 제일 처음의 노드를 가리키는 포인터이고

 head는 움직이지 않아야한다

그래야 시작이 어디인지 알수있기 때문임

//Data *head = NULL은 head를 초기화 시켜준 것.

일단 계속적으로 데이터를 받아 넣기 위해서

while문을 사용하여 4이상 적을 경우 종료되도록 만들었다.

그 다음에는 입력과 출력 삭제를 구현하기 위해

if문을 이용하여 num이 1일때는 입력, 2일때 출력, 3일때 삭제가 되도록 만들었다.

일단 1번 입력을 받기 위한 코드를 살펴보자.

if문으로 입력 받을 때, 두가지를 생각해야한다.

처음 노드에 데이터가 비어있을 경우,

head는 새로운 Data(노드)를 생성하고

head의 value에는 입력 받은 input값을 넣어주고

연결되어있는 Data가 없으니 pNext에는 NULL를 넣어준다.

아니면 처음 노드가 존재하고 다음 노드와 연결하는 경우,

head는 움직이지 말아야하기 때문에 pTemp를 만들어준다.

27번째 줄에서 pTemp는  head와 같은 곳을 가리키고 있다

(주황색은 head를 의미하고, 연두색은 pTemp를 의미)

pTemp가 pNext를 가리키면 pTemp는 pTemp->pNext가 되어야한다.

이런식으로.. while문이 종료 되면,

그자리에 새로운 데이터를 넣기 위해서

pTemp->pNext에 새로운 Data(노드)를 만들어주고

pTemp->pNext의 pNext에는 NULL을 넣어주고

pTemp->pNext의 value에는 입력 받은 input을 넣어주면

새로운 데이터를 연결하여 만들수 있다.  

이제 출력...

간단하게 설명하면 pTemp가 지나갈 때 마다 출력을 해주는 것이다.

처음에는 pTemp가 head를 가르키고 있고

다음 데이터가 NULL이 아니면

pTemp의 값을 출력하고 pTemp가 다음을 가리키도록

pTemp = pTemp->pNext를 해주는 것!

이제 삭제!

삭제가 가장 어려웠어요..

삭제를 하기 위해서는 두개의 포인터가 필요해요

그래서 pTemp1 과 pTemp2를 생성해 주고 마찬가지로 두 개다 head와 같은곳을 향하도록 해줍니다

삭제할때도 두가지로 나뉘는 데 삭제 할 값이 맨 처음에 존재하는 경우,

head를 다음으로 옮겨주고 head와 같은 곳을 가르치던 pTemp1을 삭제해주면되요!

나머지 방법은 일단 리스트에 찾고자 하는 값이 있는지 확인하기 위해서

pTemp가 NULL이 아닐 때 까지 돌려줍니다.

(NULL이 되면 리스트에 우리가 찾는 값이 없다는 것이 됨)

그리고

삭제할 값이랑 각 Data의 값이 같은지 다른지 알기 위해서 if문을 생성!

다른 경우

pTemp2 를 pTemp1 으로 바꿔줍니다.

그리고 pTemp1은 다음 Data를 가르키게 만들어줍니다. 

이제부터 시작이죠..

삭제할 값과 데이터의 값이 같은경우 

아까 다른 경우에서

pTemp2는 pTemp1의 전 위치에 존재하고 있고

pTemp1는 그 다음 데이터를 가르키고 있겠죠

삭제를 하기 위해서는 그림으로 설명하면

(파랑이 pTemp1 하늘색이 pTemp2)

이런 식으로 pTemp2의 다음이 현재 pTemp1이 가리키는 다음 데이터이어야 합니다.

그래서 다음과 같은 코드가 나왔습니다

[ pTemp2->pNext = pTemp1->pNext;]

이제 pTemp1를 지우고, NULL로 만들어주면 삭제 끝!

​

​

​

​