Doubly Linked List

Author: Dion🐱, Hamill🍔

Doubly Linked List의 형태

Singly Linked List와는 다르게 Node가 이전 Node의 참조 값을 가지고 있다.

Doubly Linked List의 장단점

• 장점

  • 역방향 탐색이 가능해짐
  • 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 링크를 사용하지 않는 한), 기본 작업은 더 비싸지만, 양방향으로 리스트에 빠르고 쉽게 순차적으로 접근할 수 있기 때문에 조작하기가 더 쉬운 경우가 많다.
  • 이중 연결 리스트에서는 해당 노드의 주소만 주어진 일정한 작업 수에 노드를 삽입하거나 삭제할 수 있다.
  • 단일 연결 리스트에서 동일한 작업을 수행하려면 해당 노드에 대한 포인터의 주소를 가지고 있어야 하며, 이 주소는 전체 리스트의 핸들(첫 번째 노드의 경우) 또는 이전 노드의 링크 필드 중 하나여야 한다.

XOR Linked List

• 어렵다...

Doubly Linked List 의 추상자료형(ADT)

• 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가 좀 더 구체적으로 머리에 들어왔어요.