159:
171:
469:(connected and sequential) portion of memory. But in a linked data structure, the reference to each node gives users the information needed to find the next one. The nodes of a linked data structure can also be moved individually to different locations within physical memory without affecting the logical connections between them, unlike arrays. With due care, a certain
461:
Compared to arrays, linked data structures allow more flexibility in organizing the data and in allocating space for it. In arrays, the size of the array must be specified precisely at the beginning, which can be a potential waste of memory, or an arbitrary limitation which would later hinder
462:
functionality in some way. A linked data structure is built dynamically and never needs to be bigger than the program requires. It also requires no guessing at creation time, in terms of how much space must be allocated. This is a feature that is key in avoiding wastes of memory.
125:
A linked list is a collection of structures ordered not by their physical placement in memory but by logical links that are stored as part of the data in the structure itself. It is not necessary that it should be stored in the adjacent memory locations. Every
537:). In some cases, linked data structures may also use more memory (for the link fields) than competing array structures. This is because linked data structures are not contiguous. Instances of data can be found all over in memory, unlike arrays.
497:
steps, slowing down the process of accessing these nodes - this sometimes represents a considerable slowdown, especially in the case of structures containing large numbers of nodes. For many structures, some nodes may require
513:. It gives us the chance to use particular space again. Memory can be utilized more efficiently by using these data structures. Memory is allocated as per the need and when memory is not further needed, deallocation is done.
81:
and other data structures that require performing arithmetic operations on pointers. This distinction holds even when the nodes are actually implemented as elements of a single array, and the references are actually array
540:
In arrays, nth element can be accessed immediately, while in a linked data structure we have to follow multiple pointers so element access time varies according to where in the structure the element is.
466:
480:
On the other hand, access to any particular node in a linked data structure requires following a chain of references that are stored in each node. If the structure has
506:−1 steps. In contrast, many array data structures allow access to any element with a constant number of operations, independent of the number of entries.
979:
655:
949:
477:
can add or delete nodes in one part of a data structure even while other processes or threads are working on other parts.
432:, which is such that in an in-order traversal of the tree the nodes are visited in ascending order of the stored values.
375:
A structure like this which contains a member that points to the same structure is called a self-referential structure.
104:, and many other widely used data structures. They are also key building blocks for many efficient algorithms, such as
888:
1023:
678:
588:
683:
58:
648:
757:
1013:
545:
499:
74:
49:
89:
Linking can be done in two ways – using dynamic allocation and using array index linking.
762:
745:
109:
961:
728:
723:
625:
183:
This is an example of the node class used to store integers in a Java implementation of a linked list:
718:
608:
522:
86:: as long as no arithmetic is done on those indices, the data structure is essentially a linked one.
39:
165:
A linked list with three nodes contain two fields each: an integer value and a link to the next node
752:
711:
641:
131:
992:
969:
565:
510:
44:
153:
A reference to the first node of the list is always kept. This is called the 'head' or 'front'.
974:
774:
383:
This is an example of the node class structure used for implementation of linked list in C++:
1018:
900:
855:
553:
534:
840:
137:
Linked list can be singly, doubly or multiply linked and can either be linear or circular.
83:
78:
16:
Set of data records (nodes) linked together and organized by references (links or pointers)
428:
A search tree is a tree data structure in whose nodes data values can be stored from some
8:
613:
Volume 7, Issue 5 (May 1964), pages 301–303. The paper originating disjoint-set forests.
470:
614:
883:
868:
733:
693:
603:
474:
444:
802:
701:
599:
530:
130:
has a data field and an address field. The
Address field contains the address of its
825:
105:
27:
845:
787:
549:
270:
This is an example of the structure used for implementation of linked list in C:
101:
937:
915:
740:
664:
526:
35:
1007:
910:
807:
792:
584:
77:
or compared for equality. Linked data structures are thus contrasted with
905:
830:
429:
97:
93:
20:
893:
797:
488:
links, there will be some nodes that cannot be reached in less than log
835:
782:
509:
Broadly the implementation of these linked data structure is through
158:
127:
70:
626:
http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf
69:
In linked data structures, the links are usually treated as special
932:
878:
706:
633:
927:
873:
314:
922:
863:
548:
that enforce the constraints of linked structures, such as the
170:
552:, many problems require more steps than in the unconstrained
525:
overhead (if nodes are allocated individually) and frustrate
944:
115:
447:
provides an ascending readout of the data in the tree.
521:
Linked data structures may also incur in substantial
441:
Objects, called nodes, are stored in an ordered set.
1005:
465:In an array, the array elements have to be in a
451:
62:). The link between data can also be called a
649:
456:
533:algorithms (since they generally have poor
656:
642:
516:
169:
1006:
484:nodes, and each node contains at most
116:Common types of linked data structures
637:
606:. An improved equivalence algorithm.
593:
578:
663:
48:) linked together and organized by
13:
178:
150:, are linked in a linear sequence.
14:
1035:
546:theoretical models of computation
378:
174:A linked list with a single node.
157:
589:The Art of Computer Programming
423:
265:
120:
92:Linked data structures include
619:
1:
571:
452:Advantages and disadvantages
7:
980:Directed acyclic word graph
746:Double-ended priority queue
559:
38:which consists of a set of
10:
1040:
18:
988:
960:
854:
816:
773:
692:
671:
609:Communications of the ACM
457:Linked list versus arrays
313:This is an example using
712:Retrieval Data Structure
385:
319:
272:
185:
19:Not to be confused with
1024:Trees (data structures)
993:List of data structures
970:Binary decision diagram
566:List of data structures
511:dynamic data structures
975:Directed acyclic graph
175:
554:random-access machine
535:locality of reference
517:General disadvantages
173:
32:linked data structure
841:Unrolled linked list
1014:Abstract data types
889:Self-balancing tree
615:ACM Digital Library
869:Binary search tree
734:Double-ended queue
604:Michael J. Fischer
445:In-order traversal
176:
1001:
1000:
803:Hashed array tree
702:Associative array
600:Bernard A. Galler
531:processor caching
523:memory allocation
167:
73:that can only be
1031:
826:Association list
658:
651:
644:
635:
634:
628:
623:
617:
597:
591:
582:
436:Basic properties
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
163:
161:
146:Objects, called
141:Basic properties
106:topological sort
102:expression trees
28:computer science
1039:
1038:
1034:
1033:
1032:
1030:
1029:
1028:
1004:
1003:
1002:
997:
984:
956:
850:
846:XOR linked list
812:
788:Circular buffer
769:
688:
667:
665:Data structures
662:
632:
631:
624:
620:
598:
594:
583:
579:
574:
562:
550:pointer machine
519:
493:
459:
454:
426:
421:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
381:
370:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
311:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
268:
263:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
181:
179:Example in Java
168:
162:
123:
118:
24:
17:
12:
11:
5:
1037:
1027:
1026:
1021:
1016:
999:
998:
996:
995:
989:
986:
985:
983:
982:
977:
972:
966:
964:
958:
957:
955:
954:
953:
952:
942:
941:
940:
938:Hilbert R-tree
935:
930:
920:
919:
918:
916:Fibonacci heap
913:
908:
898:
897:
896:
891:
886:
884:Red–black tree
881:
876:
866:
860:
858:
852:
851:
849:
848:
843:
838:
833:
828:
822:
820:
814:
813:
811:
810:
805:
800:
795:
790:
785:
779:
777:
771:
770:
768:
767:
766:
765:
760:
750:
749:
748:
741:Priority queue
738:
737:
736:
726:
721:
716:
715:
714:
709:
698:
696:
690:
689:
687:
686:
681:
675:
673:
669:
668:
661:
660:
653:
646:
638:
630:
629:
618:
592:
576:
575:
573:
570:
569:
568:
561:
558:
518:
515:
489:
458:
455:
453:
450:
449:
448:
442:
438:
437:
425:
422:
386:
380:
379:Example in C++
377:
320:
273:
267:
264:
186:
180:
177:
156:
155:
154:
151:
143:
142:
122:
119:
117:
114:
110:set union-find
36:data structure
15:
9:
6:
4:
3:
2:
1036:
1025:
1022:
1020:
1017:
1015:
1012:
1011:
1009:
994:
991:
990:
987:
981:
978:
976:
973:
971:
968:
967:
965:
963:
959:
951:
948:
947:
946:
943:
939:
936:
934:
931:
929:
926:
925:
924:
921:
917:
914:
912:
911:Binomial heap
909:
907:
904:
903:
902:
899:
895:
892:
890:
887:
885:
882:
880:
877:
875:
872:
871:
870:
867:
865:
862:
861:
859:
857:
853:
847:
844:
842:
839:
837:
834:
832:
829:
827:
824:
823:
821:
819:
815:
809:
808:Sparse matrix
806:
804:
801:
799:
796:
794:
793:Dynamic array
791:
789:
786:
784:
781:
780:
778:
776:
772:
764:
761:
759:
756:
755:
754:
751:
747:
744:
743:
742:
739:
735:
732:
731:
730:
727:
725:
722:
720:
717:
713:
710:
708:
705:
704:
703:
700:
699:
697:
695:
691:
685:
682:
680:
677:
676:
674:
670:
666:
659:
654:
652:
647:
645:
640:
639:
636:
627:
622:
616:
612:
610:
605:
601:
596:
590:
586:
581:
577:
567:
564:
563:
557:
555:
551:
547:
542:
538:
536:
532:
528:
527:memory paging
524:
514:
512:
507:
505:
501:
496:
492:
487:
483:
478:
476:
472:
468:
463:
446:
443:
440:
439:
435:
434:
433:
431:
384:
376:
374:
318:
316:
271:
184:
172:
166:
160:
152:
149:
145:
144:
140:
139:
138:
135:
133:
129:
113:
111:
107:
103:
99:
95:
90:
87:
85:
80:
76:
72:
67:
65:
61:
60:
55:
51:
47:
46:
41:
37:
33:
29:
22:
1019:Linked lists
817:
763:Disjoint-set
621:
607:
595:
585:Donald Knuth
580:
543:
539:
520:
508:
503:
494:
490:
485:
481:
479:
464:
460:
427:
424:Search trees
382:
372:
371:
312:
269:
266:Example in C
182:
164:
147:
136:
124:
121:Linked lists
98:search trees
94:linked lists
91:
88:
75:dereferenced
68:
63:
57:
53:
43:
40:data records
31:
25:
906:Binary heap
831:Linked list
430:ordered set
21:Linked data
1008:Categories
894:Splay tree
798:Hash table
679:Collection
572:References
500:worst case
467:contiguous
71:data types
50:references
950:Hash tree
836:Skip list
783:Bit array
684:Container
132:successor
128:structure
64:connector
879:AVL tree
758:Multiset
707:Multimap
694:Abstract
560:See also
544:In some
315:typedefs
59:pointers
933:R+ tree
928:R* tree
874:AA tree
556:model.
471:process
322:typedef
227:IntNode
215:IntNode
194:IntNode
84:indices
962:Graphs
923:R-tree
864:B-tree
818:Linked
775:Arrays
502:up to
475:thread
337:struct
325:struct
293:struct
275:struct
224:public
212:public
200:public
188:public
79:arrays
856:Trees
729:Queue
724:Stack
672:Types
388:class
373:Note:
245:value
206:value
191:class
148:nodes
54:links
45:nodes
34:is a
945:Trie
901:Heap
719:List
602:and
529:and
412:next
406:Node
391:Node
361:next
355:node
340:node
331:node
328:node
302:next
296:node
278:node
218:link
108:and
30:, a
753:Set
473:or
400:val
397:int
349:val
346:int
287:val
284:int
233:int
203:int
56:or
26:In
1010::
587:,
418:};
367:};
317::
308:};
134:.
112:.
100:,
96:,
66:.
657:e
650:t
643:v
611:,
504:n
495:n
491:b
486:b
482:n
415:;
409:*
403:;
394:{
364:;
358:*
352:;
343:{
334:;
305:;
299:*
290:;
281:{
260:}
257:}
254:;
251:v
248:=
242:{
239:)
236:v
230:(
221:;
209:;
197:{
52:(
42:(
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
