[뇌를 자극하는 알고리즘] 1. 리스트

자료구조: 데이터를 효울적으로 조직하고 저장하는 방법.

리스트(List): 데이터의 목록을 다루는 자료구조.

                      배열처럼 데이터집합 보관 기능을 가지면서도 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조.

노드(Node): 리스트 내의 각 요소. 데이터를 보관하는 필드와 노드와의 연결 고리 역할을 하는 포인터로 이루어짐.

                      첫 번째 노드를 헤드(Head) 마지막 노드를 테일(Tail)이라고 함. 

1. 링크드 리스트(Linked List) (단순 연결리스트)

:  노드를 연결해서 만드는 리스트. 

[링크드 리스트의 주요 연산 ]

• 노드 추가: 기존 테일의 포인터가 새로추가된 테일을 가리킴.
• 노드 탐색: 헤드부터 시작해 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근 가능.
• 노드 삭제: 삭제하고자하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 포인터에 연결.
• 노드 삽입: 노드사이 새 노드를 끼워 넣을때 앞 노드의 포인터가 새 노드를 가리키게 하고 새 노드의 포인터가 뒤 노드를 가리키게함.

노드 추가

노드 삭제

노드 삽입

링크드 리스트의 단점

-다음 노드를 가리키려는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요.

-특정 위치의 노드를 얻는데 드는 비용이 크며 속도도 느림.

 

링크드 리스트의 장점

-새로운 노드의 추가/ 삽입/ 삭제가 쉽고 빠름.

-현재 노드의 다음 노드를 얻어오는 연산에 대해 비용이 발생하지 않음.

 

결론 => 링크드 리스트는 노드의 추가/ 삽입/ 삭제는 빠르나 특정 위치에 있는 노드를 찾는 연산은 느림.

따라서 레코드의 추가/ 삽입/ 삭제가 잦고 조회는 드문 곳에 적합함.

 

2. 더블 링크드 리스트(Doubly Linked List) (이중 연결리스트)

:  양방향으로 탐색이 가능한 리스트.  자신 앞의 노드를 가리키는 포인터도 있음.

이전 노드를 가리키는 포인터를 Prev포인터(llink), 다음 노드를 가리키는 포인터를 Next포인터(rlink) 라고 하겠습니다.

 

[링크드 리스트의 주요 연산 ]  #링크드 리스트와 비슷함.

• 노드 추가: 기존 테일의 포인터가 새로추가된 테일을 가리키고 + 새로운 테일의 포인터도 기존 테일의 주소를 가리킴.
• 노드 탐색: 링크드 리스트와 같이 헤드부터 차근차근 원하는 요소에 접근 가능.
• 노드 삭제: 이전 노드의 포인터, 삭제할 노드의 양쪽 포인터, 이후 노드의 (삭제할 노드를 가리키는)포인터 모두 4개의 포인터를 다룸.삭제할 노드의 Next포인터가 가리키고 있던 노드를 앞 노드의 Next포인터가 가리키게하고, 삭제할 노드의 Prev포인터가 가리키고 있던 노드를 뒷 노드의 Prev포인터가 가리키게함. 삭제할 노드의 포인터들은 NULL로 초기화함.
• 노드 삽입: 새 노드의 Prev포인터는 앞 노드를 Next포인터는 뒷 노드를 가리킴. 앞 노드의 Next포인터와 뒷 노드의 Prev포인터는 새 노드를 가리킴.

추가

삭제

삽입

3. 환형 링크드 리스트(Circular Linked List) (원형 연결리스트)

: 헤드와 테일이 연결되어있음.  즉 헤드의 앞 노드로 테일을,  테일의 뒷 노드로 헤드를 가리킴. 

더블 링크드 리스트, 링크드 리스트로 환형 링크드 리스트를 만들 수 있음.

- 환형 더블 링크드 리스트

노드추가: 비어있는 리스트에 새 노드를 추가하면 Prev, Next포인터 모두 자기 자신을 가리킴.  비어있지 않은 경우 추가를 할 때는  테일에 붙이는 것이 아니라 테일과 헤드 사이에 삽인한다고 생각하면 편함.