1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language french
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Standard
Muchas veces necesitamos estructuras de datos cuyo tamaño puede ir cambiando
con el tiempo.
Podemos usar representaciones contiguas (tablas), pero no son eficientes
en ciertos casos porque las inserciones y eliminaciones pueden suponer
reubicaciones de elementos.
\end_layout
\begin_layout Standard
Una
\series bold
estructura de datos lineal enlazada con simple enlace
\series default
es una sucesión finita de nodos formados por un elemento y un enlace al
siguiente (o una marca de fin como
\family typewriter
NULL
\family default
si es el último).
\end_layout
\begin_layout Standard
Una estructura de este tipo se gestiona a través de un apuntador al primer
nodo, inicialmente con valor
\family typewriter
NULL
\family default
.
Podemos definir, por ejemplo, operaciones para:
\end_layout
\begin_layout Itemize
Inicializar y liberar una lista enlazada.
\end_layout
\begin_layout Itemize
Imprimir sus elementos, comprobar si contiene uno y cuál es su índice, obtener
el apuntador al nodo que contiene un elemento.
\end_layout
\begin_layout Itemize
Insertar un elemento al principio, al final, en un cierto índice o detrás
de otro dado por el apuntador al nodo.
Insertar en una lista enlazada ordenada.
\end_layout
\begin_layout Itemize
Eliminar un elemento al principio, al final, en un cierto índice o detrás
de otro dado por el apuntador al nodo.
Eliminar la primera ocurrencia de un elemento si existe, con un caso especial
por eficiencia para cuando la lista está ordenada.
\end_layout
\begin_layout Standard
Algunas de estas operaciones pueden requerir modificar el apuntador al primer
elemento, y por tanto es necesario pasarles un apuntador a dicho apuntador
(o que devuelvan el nuevo valor de este).
Para estos podemos añadir al principio un
\series bold
nodo de encabezamiento
\series default
que apunta al primer elemento
\begin_inset Quotes fld
\end_inset
real
\begin_inset Quotes frd
\end_inset
, simplificando el código a cambio de ocupar más memoria.
Por otro lado, para ciertas operaciones conviene tener apuntadores tanto
al principio como al final de la estructura enlazada.
\end_layout
\begin_layout Standard
También existen
\series bold
estructuras de datos lineales doblemente enlazadas
\series default
, en las que los nodos no apuntan sólo al siguiente elemento sino también
al anterior, permitiendo operaciones como eliminar un elemento de la lista
con un apuntador al nodo correspondiente en vez de al anterior, por ejemplo.
\end_layout
\end_body
\end_document
|
