A linked list is a data structure that consists of a sequence of elements, where each element points to the next element in the sequence. Unlike arrays, linked lists do not have a fixed size, and elements are not stored in contiguous memory locations. Each element in a linked list is called a node, and it contains data and a reference (or link) to the next node in the sequence. The last node typically points to null, indicating the end of the list.
This is a simple implementation of linked list in java programming language. Very nice and well commented java source code for novice Java programmers.
There are other implementations on Linked List in C and C++ as well.
You can “get” and “set” the list items as well as traverse through “previous” and “next ” items. This java program can create a linked list using one object or an array of objects.
This source code is just for demonstration purpose as there is already a LinkedList class available in Java.
If you need a good learning source for Java, then Head First Java is your way to go. It is a complete learning experience in Java and object-oriented programming.
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 | //**************************** //LinkedList.java //**************************** // Modified to support backwards traversal of the list. // Additions and modifications are marked by ***. public class LinkedList { private ListItem start; // First ListIem in the list. private ListItem end; // Last ListIem in the list. private ListItem current; // The current item for iterating. // Constructor to create a list containing one object: public LinkedList(Object item) { start = new ListItem(item); // item is the start current = end = start; // as well as the end and current. } // Construct a linked list from an array of objects: public LinkedList(Object[] items) { // Create a one item list: start = new ListItem(items[0]); // First item is the start end = start; // as well as the end. // Now add the other items: for (int i = 1; i < items.length; i++) addItem(items[i]); } // Add an item object to the list: public void addItem(Object item) { ListItem newEnd = new ListItem(item); // Create a new ListItem. end.setNext(newEnd); // Set next variable for old end as new end. newEnd.setPrevious(end); // So previous for new item. *** current = end = newEnd; // Store new item as end and current. *** } // Get the first object in the list: public Object getFirst() { current = start; return start.getObject(); } // Additional method to get the last object in the list: *** public Object getLast() { current = end; return end.getObject(); } // Get the next object in the list: public Object getNext() { current = current.getNext(); // Get the reference to the next item. return current == null ? null : current.getObject(); } // Additional method to get the previous object in the list: *** public Object getPrevious() { current = current.getPrevious(); // Get the reference to the previous item. return current == null ? null : current.getObject(); } } //**************************** //ListItem.java //**************************** // Modified to support backwards traversal of the list. // Additions and modifications are marked by ***. public class ListItem { ListItem next; // Refers to next item in the list. ListItem previous; // Refers to the previous item. *** Object item; // The item for this ListItem. // Constructor: public ListItem(Object item) { this.item = item; // Store the item. next = previous = null; // Set next and previous to null. *** } // Set the pointer to the next ListItem: public void setNext(ListItem next) { this.next = next; // Store reference to the next item. } // Additional method to set the pointer to the previous ListItem: *** public void setPrevious(ListItem previous) { this.previous = previous; // Store reference to the previous item. } // Get the next item in the list: public ListItem getNext() { return next; } // Additional method to get the previous item in the list: *** public ListItem getPrevious() { return previous; } // Get the object for this item: public Object getObject() { return item; } // Return class name & object: public String toString() { return "ListItem " + item; } } //**************************** //Point.java //**************************** public class Point { double x; double y; // Constructors: public Point() { x = 0.0; y = 0.0; } // Construct a Point from its coordinates: public Point(double x, double y) { this.x = x; this.y = y; } // Construct a Point from another Point: public Point(Point point) { x = point.x; y = point.y; } } |
