课程: Java Algorithms

What is a linked list? - Java教程

课程: Java Algorithms

开始一个月试用 购买团队方案

What is a linked list?

“

- [Instructor] Linked list is another common data structure that you can use to store and retrieve useful data. Similar to an array, it's a linear data structure where elements are ordered one after the other. However, with a linked list, elements are not stored at contiguous locations. Instead, they're linked using pointers. The idea of an index does not exist for linked lists. We call each element in a linked list a node. Each node contains a piece of data and a pointer to the location of the next piece of data. Several nodes can be linked together through these next pointers. In this example, the node containing 6 is the first node. It's linked to the 9 node through the next pointer, making the node containing 9 the second element of the list. The last element, 15, is linked through the 9 nodes next pointer. The last element of the list also contains a next pointer, but it points to null since there is no next element in the list. The first node in the list is often referred to as the head of the list. The last node is called the tail. Now, since the data in the linked list is not stored contiguously, the size of a linked list can vary over time. With an array, it's size must be set as soon as it's created and the size can not change. In order to store more elements in a given array, a bigger array must be created and the current items can be copied over to the larger array, along with the new items. With a linked list, this is not needed because elements are linked by pointers, which can be changed or removed at any time. For example, if you need to delete half of the data set, you can simply find the middle pointer and set it to null. This would unlink the back half of the dataset, removing it from the list. In other languages, there might be more memory cleanup required, but in Java, we have a garbage collector and this memory manager will handle it for us. Operations like these, where major data modifications can be made with just a few lines of code, make linked lists a useful tool when creating algorithms that manipulate your data.

内容