링크드 리스트란?

• Array List에 더불어 자료구조를 표현하는 대표적인 두번째 방법.
• Element 간의 연결을 이용해서 리스트를 구현 / 연결이라는 것이 핵심 키워드!!!!

메모리란?

• 메모리
  -용량이 매우 작고 전기를 끄면 데이터가 사라짐.
  -속도가 매우 빠름
• 스토리지
  -용량이 매우 크고 전기를 꺼도 데이터가 유지됨.
  -속도가 느림.
  -cpu가 스토리지에 데이터를 요구하면 속도차이가 심함. 그래서 메모리를 거쳐 로드된 데이터를 이용한다.
  -실행속도를 결정하는 것은 대체로 메모리이다. / 데이터 스트럭쳐의 미션은 메모리의 효율적인 사용
  

메모리를 건물에 비유해보자!

• 각각의 사무실의 호수 : 주소 Adress
• 메모리의 가장큰 특징은 각각의 주소에 접근하는 시간이 동일하다.
  (Random Access Memory = RAM)
• 찾고자 하는 데이터의 주소를 안다면, 빠른 속도로 데이터를 가져올 수 있는 것이 특징.
  -이 특징을 십분 활용하면 어플의 속도가 빨라짐.
  -어레이는 같은 엘리먼트들이 메모리상에 실제로 다닥다닥 붙어있음.
  -링크드는 각각의 엘리먼트들이 흩어져 있다. / 서로 연결되어 있음.
  -메모리상에서의 차이점은 위의 것들이다.

Linked List의 구조?

• 엘리먼트 하나하나가 연결되어 있음. / 내부적으로 노드 or 버텍스라고 사용함.
  -C언어에서는 구조체를 이용 / 객체 지향 언어에서는 객체를 이용하여 노드를 표현!!!
• 노드안에는 두개의 필드가 있다. / 저장되는 실제 값(Data field) / 노드다음의 노드는 무엇인가에 대한 값(Link field)
  -링크드 리스트를 이용하기 위해 알아야 하는 것은 첫번째 노드가 무엇인지 알아야함.
  -첫번째 노드가 무엇인가를 의미하는 정보를 (Head field)에 저장.
  -필드들을 다 변수라고 볼 수 있음.

Linked List를 visualgo에서 연습해보자!

• 코드상으로 표현되며 앞뒤 키로 코드 진행 단계별 확인 가능

Head 노드 추가

1.vertex라는 객체를 new로 만들었다.
2.인풋이라는 값을 인자(매개변수)로 씀.(85) -> 85라는 값을 가진 노드를 생성 -> temp라고 이름을 가지고 이 템프 노드가 85에 해당된다.
3.이 리스트에는 Head라는 변수가 있다. / 누가 그 리스트의 시작인가를 저장하는 변수
4.Head변수가 가르키는 노드는 15였다.
5.85넥스트 변수에 기존 15노드를 가리키게 하면 됨. / 85.next = head -> 2번째 콛,
6.head = temp로 헤드 값을 지정.
노드 생성 / 새로 생성한 노드의 넥스트 값을 현재 리스트의 첫번째 노드(head)를 지정 / 현재 리스트의 첫번째 노드(head)를 방금 생성한 노드로 지정

리스트 중간에 노드 추가

1.헤드를 pre 라는 임시 변수에 담는다.
2.k-1만큼 증가하며 (0~1)
3.pre변수에 pre.next(2)값을 넣는다. / 두번째 노드가 pre에 들어감.
4.aft에 세번째노드 pre.next(77)를 넣는다.
5.vtx라는 변수에 새로운 노드를 지정한다.
6.vtx.next를 aft(세번째 노드)로 지정한다.
7.pre.next를 vtx(새로운 노드)로 지정한다.
앞쪽에 있는 노드와 뒤쪽에 있는 노드의 서로 가르키는 관계를 바꿔주면 된다.

리스트 중간에 노드 삭제

1.헤드를 pre 변수에 넣는다.
2.k-1만큼 증가하며 (0~1)
3.pre변수에 pre.next값을 넣는다.
4.del변수에 pre.next를 넣고, aft변수에 del.next값을 넣는다.
5.pre.next를 aft로 지정한다. (bypass del)이 된다.
6.del변수를 지워준다.
마지막에 지워줘야 5번을 실행가능하다.
각각의 노드가 다음값의 노드를 알기 때문에 구조가 더욱 복잡하다.(점 조직)
그래서 for문을 돌리는 것이다.
Array에서는 추가하거나 지우면 기존 데이터를 밀어내야 하기 때문에 구조적으로 링크드가 낫다.

Trade Off

• Array List는 인덱스를 이용해서 주소로 직접 접근하기 때문에 속도가 빠름
  -Array List는 데이터 추가/삭제에서 element를 땡기거나 밀어내야 한다.
• Linked List는 물어가면서 주소로 접근하기 때문에 속도가 느림.
  -Linked List에서는 앞뒤 노드들의 넥스트 값만 변경하면 되어 속도가 빠름
  -Linked List에서는 노드를 메모리가 허용하는한 키울 수 있어 확장성이 좋음.
• Array List data structure에서는 해당 어레이가 갖고 있는 크기를 넘어서면 에러가남.
  공간의 낭비와 확장성이 좋지 않음.
• 이런 스트럭쳐간의 trade off를 알아야 효율적인 스트럭처를 구성할 수 있음.