🗒️ Linked List (4)

1. 2022.04.21 [Python] 원형 연결 리스트(Circular Linked List)

   원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 개념 단순 연결 리스트(Singly Linked List) 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다. 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다. 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다. 원형 연결 리스트의 원리 원형 연결 리스트의 원리 및 구조도 단순 연결 리스트와 많은 부분이 비슷하다...
2. 2022.04.21 [Python] 단순 연결 리스트(Singly Linked List)

   단순 연결 리스트(Singly Linked List) 단순 연결 리스트의 개념 선형 리스트(Linear List) 장점 배열에 구성하였기 때문에 단순하다. 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다. 프로그램으로 구현하기 비교적 쉽다. 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다. 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생) 단순 연결 리스트(Singly Linked List) 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다. 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다. 데이터와 링크로 구..
3. 2017.05.06 [C] 이중 연결 리스트(Doubly Linked List)

   이중 연결 리스트(Doubly Linked List) - 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 리스트 구조. - 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트. - 링크가 양방향이므로 양방향으로 검색이 가능해짐. - 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있음. - 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용됨. - 헤드 노드(head node)라는 특별한 노드를 추가하는 경우가 많음. - 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 의미함. cf) 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 포인터 - 헤드 노드가 존재하면 삽입, 삭제 알고리즘이 간편해짐. - 이중 연결 리스트에서의 ..
4. 2017.05.02 [C] 원형 연결 리스트(Circular Linked List)

   원형 연결 리스트(Circular Linked List) - 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트. -> 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트. - 한 노드에서 다른 모든 노드로의 접근이 가능하다는 장점이 있음. - 노드이 삽입과 삭제가 단순 연결 리스트보다는 용이해짐. - 삭제나 삽입 시에는 항상 선행 노드의 포인터가 필요함. - 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있음. 코드 // 원형 연결 리스트 (Circular Linked List) #include #include typedef int element; typedef struct ListNode { element data; struct ListNo..