<자료구조> 역순 연결 리스트

 

🎯

 

{ 역순 연결 리스트 }

연결 리스트

1. 요소들끼리 붙어 있지 않고 서로의 위치정보를 포인터로 가지고 있습니다.

2. 맨 앞의 헤드 요소의 주소만 알 수 있기 때문에 특정요소를 찾기 위해서는 맨 앞에서부터 하나씩 타고 갑니다.

3. 요소를 추가하기가 비교적 쉽습니다(포인터만 수정하면 됨).

 

배열

1. 요소들끼리 다닥다닥 붙어있습니다

2. 인덱스를 통해서 원하는 요소를 바로 찾을 수 있습니다.

3. 요소를 추가하기가 어렵습니다(요소들의 위치를 하나씩 움직여야 함).

 

연결리스트 vs 배열

	연결 리스트	배열
장점	1. 추가/삭제 빠름 2. 크기가 동적 3. 효율적인 메모리 할당/이용	1. 탐색 시간 빠름 2. 노드당 메모리 적음 3. 캐시 지역성이 좋음
단점	1. 탐색 시간 느림 2. 노드별 메모리 더 소모     (포인터를 같이 저장해야 함)	1. 추가/삭게 느림 2. 크기가 고정 3. 비효율적인 메모리 할당/이용

 

역순 연결 리스트

연결 리스트를 거꾸로 만들어봅니다.

코드로 먼저 확인하겠습니다.

    def reverse_list(head: ListNode) -> ListNode:
        node = head
        prev = None

        while node:
            next = node.next
            node.next = prev

            prev = node
            node = next

        return prev

 

개념은 익힌거 같으나 정작 활용하려니 떠오르지 않아서 그림으로 정리해 보았습니다

01234567891011121314

 

📌

 

https://dev.to/gisakaze/difference-between-linked-list-and-array-462e

Difference between Linked List and Array in CPP

https://www.youtube.com/watch?v=TSDl7sRxWdU