연결 리스트7 [Javascript] 연결 리스트 자료구조를 다시 복습할 겸, 알고리즘 포스팅에 활용도 하기 위해 자바스크립트로 다시 자료구조를 써보려고 합니다. 자료구조의 설명 자체는 기존 링크를 달기로 하고, 구현 방식은 조금 다르게 만들어 보기로 했습니다. 2021.09.03 - [Programming/자료구조] - 연결 리스트 Linked List 연결 리스트 Linked List 선형 리스트는 일반적인 배열과 다를바 없으므로 다시 작성하는 자료구조에서는 넘어가고 바로 연결 리스트부터 공부를 시작하겠습니다. 0. 연결 리스트 연결 리스트는 선형 리스트와는(순차 bamtory29.tistory.com class Node { constructor(data, nextNode = null) { this.data = data; this.nextNode =.. 2021. 11. 17. 이중 연결 리스트 Doubly Linked List 이번에 소개할 자료구조는 이중 연결 리스트 입니다. 1. 이중 연결 리스트 이중 연결 리스트 혹은 양방향 연결 리스트라고 불리우는 이 자료도 연결 리스트의 일종입니다. 지난번 원형 연결 리스트와 마찬가지로 한 가지 개념만 추가하면 되는데요. 바로 링크필드가 양옆에 있다는 점입니다. 지난번 까지 알아본 리스트의 노드들은 다음과 같이 구성되어있었습니다. 하지만 양방향 링크 필드의 노드는 다음과 같이 구성됩니다. 편의상 앞의 링크 필드는 '왼쪽 링크 필드', 뒤의 링크 필드는 '오른쪽 링크 필드'라고 명명하고 넘어가겠습니다. 왼쪽 링크 필드는 현재 노드의 이전 노드를 가리키고, 오른쪽 링크 필드는 현재 노드의 다음 노드를 가리킵니다. 이렇게 한 노드에서 양방향의 링크를 가리킨다 해서 양방향, 선모양으로 펼쳐놓.. 2021. 9. 10. 원형 연결 리스트 이번에 소개할 자료구조는 원형 연결 리스트입니다. 1. 원형 연결 리스트 소개 원형이라는 이름에서 볼 수 있듯이 동그란 형태를 가진 연결 리스트입니다. 하지만 연결 리스트 소개에서 이야기 했듯이 실제 물리적으로 원형이 아니라 처음과 끝이 이어져 있기 때문에 원형이라고 불리우는 것 입니다. 지난번 까지 배운 연결 리스트는 head 노드와 tail 노드가 정해져 있어서 시작과 끝이 확실한 하나의 선 같은 구조였습니다. 그러나 원형 연결 리스트는 끝의 주소 필드가 처음을 가리켜서 마치 원형처럼 보이게 됩니다. 2. 노드 정의 노드 구조 자체는 연결리스트와 같이 [데이터 필드-링크 필드] 쌍으로 이루어져있기 때문에 지난번 노드 정의와 다르지 않습니다. typedef struct ListNode { char da.. 2021. 9. 8. 연결 리스트 Linked List 선형 리스트는 일반적인 배열과 다를바 없으므로 다시 작성하는 자료구조에서는 넘어가고 바로 연결 리스트부터 공부를 시작하겠습니다. 0. 연결 리스트 연결 리스트는 선형 리스트와는(순차 자료구조) 다르게 자료의 순서가 존재하지 않는 자료구조 입니다. 순서가 없는 자료구조를 저장하는 방식은 노드(포인터)를 이용하는 방식입니다. 자료는 데이터 필드와 링크 필드 한 쌍으로 구성되어 있는데 데이터에는 실질적으로 사용될 데이터가 있고 링크 필드는 다음 데이터의 주소를 가리키는 정보가 담겨있습니다. 그래서 이것을 그림으로 풀어보면 다음과 같은 모양으로 구성되어있습니다. 이런식으로 연결되있어서 연결 리스트라고 불리우게 됩니다. 그러면 지금부터 노드 구현, 삽입, 삭제를 구현해보도록 하겠습니다. 1. 노드 정의 노드를 구.. 2021. 9. 3. [Data Structure] 연결 리스트 구현 연결 리스트에는 단순, 원형, 이중 연결리스트 등이 존재합니다. 오늘은 이 중 첫 번째인 단순 연결 리스트를 구현해보도록 하겠습니다. 1. 노드 생성 우선 제일 먼저 할 일은 노드를 생성하는 부분을 구현하는 것 입니다. 지난 포스트에서 소개한 노드의 구조를 보면 다음과 같이 데이터와 링크 필드 두가지로 구현되어 있습니다. public class LinkedList { private class Node { //노드 private Object data;//데이터 필드 private Node next;//링크 필드 public Node(Object input) { this.data = input; this.next = null; } } //첫 번째 노드 private Node head; //마지막 노드 pri.. 2021. 6. 28. [Data Structure] 연결 리스트(Linked List) 지난번에 선형 리스트에 대해서 소개를 했습니다. 그러나 선형 리스트는 배열이기 때문에 크기가 정해져있다는 큰 문제점을 가지고 있었습니다. 이점을 보완한 구조가 연결 리스트입니다. 1. 연결 리스트 연결 리스트는 노드로 이루어진 리스트 입니다. 선형 리스트와 다르게 자료의 물리적 순서와 논리적인 순서가 일치하지 않아도 된다는 점이 있으며, 각 자료들은 노드를 통해 저장되고 연결되어있습니다. 연결 리스트는 단순, 원형, 이중 연결과 같은 여러 방식이 있으며 여러 포스트에 걸쳐서 차차 소개해나가도록 하겠습니다. 2. 노드의 구조 리스트 첫 시간에도 설명했지만 노드는 다음과 같은 구조를 가지고 있습니다. 링크 필드가 다음 노드를 가리키고 있고 이것들이 이어져서 리스트를 구성하는 방식이었죠. 이러한 노드를 구현해.. 2021. 6. 25. 이전 1 2 다음 300x250
