# Linked List

👉Linked List

ArrayList와 다르게 element간의 연결을 이용해서 List를 구현한 것

linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것!!

ArryaList에서는 element라는 이름을 사용했지만, Linked List와 같이 연결된 element들은 Node, 마디 혹은 Vertex, 정점이라고 부른다.

Node는 실제 정보를 담고 있는 하나의 단위이며, Link는 노드간의 위치정보를 저장하여 서로 연결해줄 수 있는 연결고리

Linked List가 실행될 때 이미지

이미지 출처 : wikipedia

Arraylist vs Linkedlist

Arraylist와 Linkedlist 비교 이미지

< 이미지 출처 : https://opentutorials.org/module/1335/8821 >

Node

노드는 자료와 다음 노드를 가리키는 참조값으로 구성

Linked List 구현

초기화(init) / 삽입(insert) / 삭제(Remove) 작업 필요

ex) 자바스크립트에서 생각할 수 있는 Linked List는 array가 있다. 따라서 array 메서드를 이용해서 array.push()를 이용하여 데이터를 추가할 수 있고, array.splice()를 이용하여 데이터를 제거할 수 있다.

Linked List 초기화

노드를 접근하기 위해서는 맨 처음 노드의 주소를 가리킬 노드가 필요

첫번째 노드를 Head 표현 / 마지막 노드를 Tail 표현

• 초기화 과정에서 다음 주소를 가리키는 포인터를 null로 설정

Linked List 메서드

• find() : head노드부터 차례로 해당 item을 검색하면서 찾고 찾으면 해당 노드 반환

• insert() : find()메서드로 찾은 노드 뒤에 새로운 노드를 연결

  

  < 이미지 출처 : https://untitledtblog.tistory.com/82?category=689662 >

  But 중복값을 허용하기 때문에 중복된 값을 넣다보면 처음 찾아낸 노드 뒤에 연결하는 에러가 발생할 수 있다.

• first() : head노드부터 차례로 해당 item을 검색하면서 찾고 찾으면 해당 노드 반환

• append() : 맨 뒤에 노드를 추가

  

  < 이미지 출처 : https://untitledtblog.tistory.com/82?category=689662 >

• next() : 다음에 연결할 노드 검색

• delete() : 현재 해당 노드를 삭제

  

  < 이미지 출처 : https://untitledtblog.tistory.com/82?category=689662 >

• remove() : 삭제할 노드 바로 직전에 있는 노드를 찾아 연결을 끊어버리는 것으로 삭제처리

장점: 노드의 포인터를 통해서 모든 데이터의 참조가 가능, 링크 이동을 통한 유연한 변경이 가능

단점 : 데이터의 위치를 알아도 바로 접근 불가, 정렬속도가 느리다.