연결리스트(Linked List)

데이터가 많아지면 그룹 관리의 필요성 ---> 자료의 열거형 표현

- 배열 : 하나의 변수에 여러정보를 담기 가능, 반복문등과 결합해 처리 용이, 인덱스를 가지며

               따라서 자료의 빠른 조회가 가능하다. 자료의 접근에 시간복잡도 O(1)이다.

 

- 리스트 : 배열은 크기가 고정적이며, 값의 수정이 번거롭다.(수정시 수정인덱스 이후의 값의 인덱스를 조정해야함)

                위의 한계를 해결하는것이 연결리스트(Linked List). 값을 동적으로 생성된 노드에 저장해 자료들간의 연결관 계  구성.  공간적제                  약을 덜 받고 자료의 수정삭제가 쉽다. 하지만 자료의 접근성에있어 시간복잡도 O(N)을 띄게 된다.

 

 

자료의 접근(get)은 ArrayList가 좋다. 하지만 자료를 삭제함에 있어 연결리스트가 더 좋다고 할수있다.

 

 

 

 

연결리스트의 각노드에는 data값과 다음 노드의 주소를 가지게 된다.

head부분은 데이터가 있어도되고 없어도되며 없을경우가 코드를 구성하기 더 쉽다.

이경우 head는 어떤 기능도 하지않는 더미노드(dummy node)가 된다.

 

아래코드와 함께 살펴보자

 

먼저 연결리스트의 정의부분이다.

listNode라는 것을 구조체로 선언하는데 위에보면 listNode 형의 포인터인 listPointer가 선언된다.

이렇게 포인터변수를 하나 선언해놓으면 프로그램작성이 조금더 간단해진다고 할 수 있다.

struct listNode *= listPointer 이다.

 

먼저 프로그램은 임의의 수들을 파일입력으로 넣는데, 이를 오름차순정렬인 리스트로 만드는 프로그램이다.

find는 리스트 노드가 한개 들어갈때마다 들어갈 위치를 정해준다. 여기선 계속해서 link(=next)로 넘어가다가

자신보다 높은 값을 가진 노드를 만나면 그 앞에 넣으면 된다. 반환은 넣을위치 이전노드를 반환해야 insert가 쉽게

가능. 처음에는 first가 비었기때문에 NULL을반환.

 

 

더미노드를 만들지 않아, 상당히 까다로워졌다.

first가 맨첫 노드인데, 맨 첫노드를 넣을때 x가 null 이면 first가 첫노드로 생성, 또 x가 first라면 first다음에 노드를

넣어주기 위해 경우의수 하나를또 생성한다. 그 이후엔 반복문을 통해 할 수 있다.

 

 

delete를 통해 50이하의 항목들은 모두 지워보았다.

delete작업또한 first가 첫번째 항목이므로 이또한 예외처리를 해주었다.

물론 다른방식으로도 작성할 수있다. 이방식으로 하면 delete함수의 else함수가 쓸모없게된다.

 

 

 

더미노드 방식으로 하면 훨씬 간단해진다.

 

이전에 했던 많은 경우의수가 사라지고, 그냥 first다음부터 차례대로 넣어주면 된다.