[Data Structure] Linked List

Linked List

---

Linked List는 List 구현 클래스이므로 Array List와 사용 방법은 똑같지만 내부 구조는 완전 다르다.

Array List는 내부 배열에 객체를 저장해서 인덱스로 관리 하지만, Linked List는 인접 참조를 링크해서 체인처럼 관리한다.

Linked List 구조

Linked List는 노드(엘리먼트)들의 모임이다.

따라서 내부적으로 노드를 가지고 있어야 한다.

Array List의 경우 엘리먼트가 배열의 엘리먼트 였지만 Linked List는 배열 대신에 다른 구조를 사용한다.

노드는 최소한 두가지 정보를 알고 있어야 한다. 노드의 값과 다음 노드이다.

각각의 노드가 다음 노드를 알고 있기 때문에 하나의 연결 된 값의 모임을 만들 수 있는 것이다.

이것을 구현하는 방법은 여러가지 이다.

만약 사용언어가 C라면 구조체, 자바와 같은 객체지향 언어라면 객체에 데이터 필드와 링크 필드를 만든다. 보통 데이터 필드는 value라는 이름의 변수, 링크 필드는 next 변수를 사용한다.

value에는 노드의 값이 저장되고, next에는 다음 노드의 포인터나 참조 값을 저장해서 노드와 노드를 연결 시키는 방법을 사용한다.

● 데이터의 추가

새로운 노드를 생성한다.

Vertex temp = new Vertex(input)

새로운 노드의 다음 노드로 첫번째 노드를 가리킨다

temp.next = head

head = temp

● 중간에 추가

head를 참조해서 첫번째 노드를 찾는다.

Vertex temp1 = head

23의 자리에 새로운 노드를 위치시키기 위해서는 6을 알고 있어야 한다. 6의 next로 새로운 노드를 지정해야 하기 때문이다.

6을 temp1로 지정하기 위해 반복문

//현재 k의 값은 2
while (--k!=0)
  temp1 = temp1.next

6의 next를 이용해서 23을 찾아서 temp2로 지정한다.

Vertex temp2 = temp1.next

값이 90인 새로운 노드를 생성한다

Vertex newVertex = new Vertex(input)

새로운 노드의 다음 노드로 23번을 지정한다.

newVertex.next = temp2

추가 되었다.

● 데이터의 삭제

head를 이용해서 첫번째 노드를 찾는다

Vertex cur = head

두번째 노드로 이동한다

//k = 2
while (--k!=0)
  cur = cur.next

세번째 노드를 찾는다.

Vertex tobedeleted = cur.next

두번째 노드의 next를 23으로 변경한다.

cur.next = cur.next.next

90을 삭제해서 메모리에서 제거한다.

delete tobedeleted