Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
m (Exchanged start/end) |
|||
| Line 650: | Line 650: | ||
? list |
? list |
||
# value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20></lang> |
# value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20></lang> |
||
=={{header|fortran}}== |
|||
<lang fortran> |
|||
module dlist |
|||
implicit none |
|||
type node |
|||
type(node), pointer :: next => null() |
|||
type(node), pointer :: prev => null() |
|||
integer :: data |
|||
end type node |
|||
type dll |
|||
type(node), pointer :: head => null() |
|||
type(node), pointer :: tail => null() |
|||
integer :: num_nodes = 0 |
|||
end type dll |
|||
public :: node, dll, append, prepend, insert, dump, reverse_dump, tidy |
|||
private :: init |
|||
contains |
|||
! Create a new doubly-linked list |
|||
type(dll) function new_dll() |
|||
new_dll = dll() |
|||
return |
|||
end function new_dll |
|||
! Append an element to the end of the list |
|||
subroutine append(dl2, value) |
|||
type(dll), intent(inout) :: dl2 |
|||
integer, intent(in) :: value |
|||
type(node) :: element |
|||
type(node), pointer :: np |
|||
! If the list is empty |
|||
if (dl2%num_nodes == 0) then |
|||
call init(dl2, value) |
|||
return |
|||
end if |
|||
! Add new element to the end |
|||
dl2%num_nodes = dl2%num_nodes + 1 |
|||
np => dl2%tail |
|||
allocate(dl2%tail) |
|||
dl2%tail%data = value |
|||
dl2%tail%prev => np |
|||
dl2%tail%prev%next => dl2%tail |
|||
end subroutine append |
|||
! Prepend an element to the beginning of the list |
|||
subroutine prepend(dl2, value) |
|||
type(dll), intent(inout) :: dl2 |
|||
integer, intent(in) :: value |
|||
type(node) :: element |
|||
type(node), pointer :: np |
|||
if (dl2%num_nodes == 0) then |
|||
call init(dl2, value) |
|||
return |
|||
end if |
|||
dl2%num_nodes = dl2%num_nodes + 1 |
|||
np => dl2%head |
|||
allocate(dl2%head) |
|||
dl2%head%data = value |
|||
dl2%head%next => np |
|||
dl2%head%next%prev => dl2%head |
|||
end subroutine prepend |
|||
! Insert immediately before the given index |
|||
subroutine insert(dl2, index, value) |
|||
type(dll), intent(inout) :: dl2 |
|||
integer, intent(in) :: index |
|||
integer, intent(in) :: value |
|||
type(node), pointer :: element |
|||
type(node), pointer :: np1, np2 |
|||
integer :: i |
|||
if (dl2%num_nodes == 0) then |
|||
call init(dl2, value) |
|||
return |
|||
end if |
|||
! If index is beyond the end then append |
|||
if (index > dl2%num_nodes) then |
|||
call append(dl2, value) |
|||
return |
|||
end if |
|||
! If index is less than 1 then prepend |
|||
if (index <= 1) then |
|||
call prepend(dl2, value) |
|||
return |
|||
end if |
|||
! Find the node at position 'index' counting from 1 |
|||
np1 => dl2%head |
|||
do i=1, index-2 |
|||
np1 => np1%next |
|||
end do |
|||
np2 => np1%next |
|||
! Create the new node |
|||
allocate(element) |
|||
element%data = value |
|||
! Connect it up |
|||
element%prev => np1 |
|||
element%next => np2 |
|||
np1%next => element |
|||
np2%prev => element |
|||
dl2%num_nodes = dl2%num_nodes + 1 |
|||
end subroutine insert |
|||
subroutine dump(dl2) |
|||
type(dll), intent(in) :: dl2 |
|||
type(node), pointer :: current |
|||
integer :: i |
|||
write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - fwd = ' |
|||
current => dl2%head |
|||
i = 1 |
|||
write(*,fmt='(i0,a)',advance='no') current%data,', ' |
|||
do |
|||
current => current%next |
|||
if (.not. associated(current)) then |
|||
exit |
|||
end if |
|||
i = i + 1 |
|||
if (i == dl2%num_nodes) then |
|||
write(*,'(i0)') current%data |
|||
else |
|||
write(*,fmt='(i0,a)',advance='no') current%data,', ' |
|||
end if |
|||
end do |
|||
end subroutine dump |
|||
subroutine reverse_dump(dl2) |
|||
type(dll), intent(in) :: dl2 |
|||
type(node), pointer :: current |
|||
integer :: i |
|||
write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - bwd = ' |
|||
current => dl2%tail |
|||
write(*,fmt='(i0,a)',advance='no') current%data,', ' |
|||
i = 1 |
|||
do |
|||
current => current%prev |
|||
if (.not. associated(current)) then |
|||
exit |
|||
end if |
|||
i = i + 1 |
|||
if (i == dl2%num_nodes) then |
|||
write(*,'(i0)') current%data |
|||
else |
|||
write(*,fmt='(i0,a)',advance='no') current%data,', ' |
|||
end if |
|||
end do |
|||
end subroutine reverse_dump |
|||
! Deallocate all allocated memory |
|||
subroutine tidy(dl2) |
|||
type(dll), intent(in) :: dl2 |
|||
type(node), pointer :: current, last |
|||
current => dl2%head |
|||
do |
|||
last => current |
|||
current => current%next |
|||
if (associated(last)) then |
|||
deallocate(last) |
|||
end if |
|||
if (associated(current, dl2%tail)) then |
|||
deallocate(current) |
|||
exit |
|||
end if |
|||
end do |
|||
end subroutine tidy |
|||
subroutine init(dl2, value) |
|||
type(dll), intent(inout) :: dl2 |
|||
integer, intent(in) :: value |
|||
allocate(dl2%head) |
|||
dl2%tail => dl2%head |
|||
dl2%tail%data = value |
|||
dl2%num_nodes = 1 |
|||
return |
|||
end subroutine init |
|||
end module dlist |
|||
program dl |
|||
use dlist |
|||
implicit none |
|||
type(dll) :: mydll |
|||
mydll = new_dll() |
|||
call append(mydll, 5) |
|||
call append(mydll, 7) |
|||
call prepend(mydll, 3) |
|||
call prepend(mydll, 1) |
|||
call insert(mydll, 3, 4) |
|||
call dump(mydll) |
|||
call reverse_dump(mydll) |
|||
call tidy(mydll) |
|||
end program dl |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
Doubly-linked list has 5 element - fwd = 1, 3, 4, 5, 7 |
|||
Doubly-linked list has 5 element - bwd = 7, 5, 4, 3, 1 |
|||
</pre> |
|||
=={{header|F Sharp|F#}}== |
=={{header|F Sharp|F#}}== |
||