TIL(Today I Learn) - #4. Data Structure - Linked List

Linked List에 대해 알아보도록 하겠습니다.

Linked List란 이전 node에 다음 node의 메모리 주소 값이 저장되어 연결된 Data Structure를 말합니다.

Linked List Data structure의 methods

• search()
• insert()
• remove()
  

Linked List Data structure의 property

• head, size

Linked List 이미지

Linked List 구현

pseudo code

- search() 
if empty, return NOT_FOUND
index = 0, temp = head
while (temp.item != v)
  index++, temp = temp.next
  if temp == null
    return NOT_FOUND
return index

- insert() 
Vertex pre = head
for (k = 0; k < i-1; k++)
  pre = pre.next
Vertex aft = pre.next
Vertex vtx = new Vertex(v)
vtx.next = aft
pre.next = vtx

- remove()
if empty, do nothing
Vertex pre = head
for (k = 0; k < i-1; k++)
  pre = pre.next
Vertex del = pre.next, aft = del.next
pre.next = aft // bypass del
delete del