ใณใณใใฅใผใฟใตใคใจใณในใซใใใฆใๅๆนๅใชในใใฏใใผใใจๅผใฐใใไธ้ฃใฎใชใณใฏใฌใณใผใใใใชใ้ฃ็ตใใผใฟๆง้ ใงใใๅใใผใใฏใชใณใฏใจๅผใฐใใ2ใคใฎใใฃใผใซใใๆใฃใฆใใฆใใใใใฏไธ้ฃใฎใใผใๅ ใซใใใๅใฎใใผใใจๆฌกใฎใใผใใๅ็ งใใฆใใพใใๆๅใฎใใผใใฎๅใฎใชใณใฏใจๆๅพใฎใใผใใฎๆฌกใฎใชใณใฏใฏใใ็จฎใฎ็ต็ซฏใ็คบใใฆใใฆใไธ่ฌ็ใซใฏใใใผใใผใใnullใๆ ผ็ดใใใใชในใใฎใใฉใใผในใๅฎนๆใซ่กใใใใใซใใฆใใพใใใใใใใผใใผใใ1ใคใใใชใๅ ดๅใใชในใใฏใใฎ1ใคใฎใใผใใไปใใฆๅพช็ฐ็ใซใชใณใฏใใใพใใใใใฏใใใใใ้ใฎ้ ็ชใฎๅๆนๅใฎใชใณใฏใชในใใ2ใคใใใใฎใจใใฆ่ใใใใจใใงใใพใใ
2ใคใฎใชใณใฏใซใใใใชในใใใฉใกใใฎๆนๅใซใใใฉใใผในใใใใจใใงใใพใใๅๆนๅใชในใใฏใใผใใฎ่ฟฝๅ ใๅ้คใฎ้ใซใ็ๆนๅใชใณใฏใชในใใจๆฏในใฆใใๅคใใฎใชใณใฏใๅคๆดใใๅฟ ่ฆใใใใพใใใใใใใใฎๆไฝใฏ็ฐกๅใงใใใๅน็็ใช(ๆๅใฎใใผใไปฅๅคใฎๅ ดๅ)ๅฏ่ฝๆงใใใใพใใๅใฎใใผใใฎใชใณใฏใๆดๆฐใใ้ใซๅใฎใใผใใไฟๆใใใใๅใฎใใผใใ่ฆใคใใใใใซใชในใใใใฉใใผในใใๅฟ ่ฆใใใใพใใใ
Add(value)
Pre: value is the value to add to the list
Post: value has been placed at the tail of the list
n โ node(value)
if head = รธ
head โ n
tail โ n
else
n.previous โ tail
tail.next โ n
tail โ n
end if
end Add
Remove(head, value)
Pre: head is the head node in the list
value is the value to remove from the list
Post: value is removed from the list, true; otherwise false
if head = รธ
return false
end if
if value = head.value
if head = tail
head โ รธ
tail โ รธ
else
head โ head.next
head.previous โ รธ
end if
return true
end if
n โ head.next
while n = รธ and value !== n.value
n โ n.next
end while
if n = tail
tail โ tail.previous
tail.next โ รธ
return true
else if n = รธ
n.previous.next โ n.next
n.next.previous โ n.previous
return true
end if
return false
end Remove
ReverseTraversal(tail)
Pre: tail is the node of the list to traverse
Post: the list has been traversed in reverse order
n โ tail
while n = รธ
yield n.value
n โ n.previous
end while
end Reverse Traversal
| Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(n) | O(n) | O(1) | O(n) |
O(n)