Doubly Linked List
Author: Dion🐱, Hamill🍔
Singly Linked List와는 다르게 Node가 이전 Node의 참조 값을 가지고 있다.
-
장점
- 역방향 탐색이 가능해짐
- index 탐색을 할 때, 항상 정방향으로만 탐색을 했는데, 역방향 탐색이 가능해져서 탐색하는데 걸리는 시간이 절반으로 줄어들었음
- 역방향 탐색이 효율이 좋아져서, 손해없이 역방향 탐색이 가능합니다.
-
단점
- node가 payload를 2개를 가지고 있어서 데이터가 커진다.
- Singly Linked List에 비해서 구현이 복잡하다.
-
Doubly linked list
- 이중 연결 리스트에서 각 노드는 다음 노드 링크 외에 순서에서 '이전' 노드를 가리키는 2 번째 링크 필드를 포함한다.
- 이 두 링크는 'forward(전방)'과 'backwards(후방)' 또는 'next(다음)'과 'prev(previous 이전)'으로 불릴 수 있다
정수 값, 다음 노드로 향하는 링크, 이전 노드로 가는 링크 3 개의 필드가 포함된 이중 연결 리스트 -
많은 현대 운영 체제는 active processes, 스레드 및 기타 동적 객체에 대한 참조를 유지하기 위해 이중 연결 리스트를 사용합니다.
-
Doubly linked vs. singly linked
- 이중 연결 리스트는 노드 당 더 많은 공간을 필요로 하며 (XOR 링크를 사용하지 않는 한), 기본 작업은 더 비싸지만, 양방향으로 리스트에 빠르고 쉽게 순차적으로 접근할 수 있기 때문에 조작하기가 더 쉬운 경우가 많다.
- 이중 연결 리스트에서는 해당 노드의 주소만 주어진 일정한 작업 수에 노드를 삽입하거나 삭제할 수 있다.
- 단일 연결 리스트에서 동일한 작업을 수행하려면 해당 노드에 대한 포인터의 주소를 가지고 있어야 하며, 이 주소는 전체 리스트의 핸들(첫 번째 노드의 경우) 또는 이전 노드의 링크 필드 중 하나여야 한다.
- 어렵다...
- Node 생성
- 설명 : 노드를 생성한다.
- 메소드 명 : constructor
- 매개변수 :
- 리턴 값 :
- Node 추가
- 설명: Node를 맨 뒤에 추가한다.
- 메소드 명: add
- 매개변수: Node node
- 리턴 값: void
- Node 삽입
- 설명 : 노드를 중간에 삽입한다.
- 메소드 명 : insert
- 매개변수 : int input
- 리턴 값 : void
- Node 삭제
- 설명: 해당하는 Node를 찾아서 제거한다. || 해당하는 Index의 Node를 찾아서 제거한다.
- 메소드 명: remove
- 매개변수: Node node, int index
- 리턴 값: void
- Node 탐색
- 설명: 해당하는 Node를 찾아서 index를 반환한다.
- 메소드 명: search
- 매개변수: Node node, int index
- 리턴 값: int index, Node node
- List 개수
- 설명 : 노드의 개수를 반환한다.
- 메소드 명 : size
- 매개변수 :
- 리턴 값 : int
- Node 인덱스 데이터 가져오기
- 설명: 해당하는 index의 Node를 반환한다.
- 메소드 명: search
- 매개변수: int index
- 리턴 값: Node node
- Node Iterator
- 다음 Node가 있는지 여부
- Node previous
https://opentutorials.org/module/1335/8941
-
Hamill
- 인원 충당이 시급(내가 설렁설렁하기 위해)
- 오늘 너무 열심히 해서 자동 배포 못할 듯
- 일주일에 하나씩 자료 구조에 대해 생각하고 구현해보는 시간을 가졌더니 구현한 자료구조를 잊지 않을 것 같음(물론 구현 코드나 정확한 원리는 잊어버릴 거 같지만)
- 좋은 스터디 사례를 참고해서 좋은 스터디가 됐으면 합니다
-
Dion
- 에버루상 연락이 없어서 시무룩...
- 오늘 왜이리 졸릴까요...
- 구현해보면서 이렇게 구현할 수 있겠구나를 느꼈어요.
- Linked List가 좀 더 구체적으로 머리에 들어왔어요.