03. 연결리스트

1. 연결리스트 구조

 

head : 최초에 노드의 주소를 담으며 더미노드(아무것도 없는 빈 껍데기 노드)를 만들어 구현한다.

           -> Node { int data, Node next }

           -> 가리키는 주소가 절대 변경되면 안된다. (링크가 깨짐)

 

Tail : 이중 연결리스트에 필요, 노드의 맨 끝을 가리킨다. 

key(data) : data를 담을 일반 변수

next(&) : 다음 노드의 주소를 담을 포인터 변수(Java 에서는 포인터변수 개념이 없기 때문에 객체로 대체한다.)

 

=> 위의 개념을 바탕으로 [삽입,삭제,탐색]을 구현한다. 

=> 맨뒤에 삽입(addLast), 맨앞에 삽입(addFirst), 맨뒤에 삭제(removeLast), 맨앞에 삭제(removeFisrt),

     중간에 삽입(insertNode), 중간에 삭제(dropNode), 탐색(searchNodeData)

      

2. 연결리스트 종류

1) 단일 연결리스트 (정방향)

    a. 최초 연결일 경우

        head의 next가 null을 가리키므로 그냥 단순히 다음노드의 주소를 head의 next에 대입(연결)해주기만 하면 된다. 

   

    b. 이미 연결된 경우 (addFisrt)

        1) 새로 삽입할 노드의 next에 head의 next를 대입(연결)하여 연결한다. 

        2) head의 next에 새로 삽입할 노드를 대입(연결)하여 연결한다. 

 

     c. 이미 연결된 경우 (addLast)

         1) 정석적인 방법은 head부터 시작해서 노드를 전부 타고 들어간 뒤(순차탐색) null을 가리키는

             노드를 찾는다.

         2) 탐색한 마지막 노드의 next에 삽입할 노드를 대입(연결)한다.

         3) 삽입한 노드의 next에 null을 대입(연결)한다. 

 

     d. 이미 연결된 경우 (insertNode)

         1) 주어진 데이터를 먼저 찾는다. 

         2) 삽입할 노드의 next에 현재 node의 next를 대입(연결)한다.

         3) 현재 node의 next에 삽입할 node를 대입(연결)한다.

    e. 맨 앞의 삭제

        1) head의 next에 삭제 대상의 next를 대입(연결)한다. 

        2) 삭제 대상을 소거한다.

            -> java의 경우, head(1번째 노드)에 head.next(다음 노드)를 대입하면 끝이다. 

 

 

   f. 맨 뒤의 삭제

      1) 노드의 next의 next가 null인 노드를 찾는다.

      2) 노드의 next에 null를 대입(연결)한다. 

 

2) 이중 연결리스트 (양방향)

단일 연결리스트와 동작은 동일하지만, 이전 노드의 주소를 가리키는 Prev 포인터 변수가 추가되었다.

역방향 참조가 가능하게 된 것이다.

이 때, Tail이라는 더미 노드를 선택적으로 추가할 수 있는데 제일 끝 노드를 가리킨다. 

 

  a. 삽입

      1) 삽입할 노드 next -> head의 next 대입(연결)

      2) head의 next -> 삽입할 노드를 대입한다. 

      3) 삽입할 노드 prev -> head를 대입

      4) 삽입할 노드 next의 prev -> 삽입할 노드 대입(연결)

 

 

3) 원형 연결리스트

 

Head, Tail이 반드시 필요하며 Tail이 head를 가리키며, Head, Tail은 절대 불변이다.