Do nodes contain 3 pieces of data in this LinkedList?

Posted on 2011-10-24
Last Modified: 2012-05-12
My algorithms & data structures textbook has an implementation of LinkedList. I'm looking at lines 8 through 16 the java code below. So, the node is comprised of three parts: the data (in the form of an object), the previous node, and the next node, is that correct?
public class MyLinkedList<AnyType> implements Iterable<AnyType> {

	private int theSize;
	private int modCount = 0;
	private Node<AnyType> beginMarker;
	private Node<AnyType> endMarker;

	private static class Node<AnyType> 
		public Node( AnyType d, Node<AnyType> p, Node<AnyType> n ) {
			data = d; prev = p; next = n;}

		public AnyType data; 
		public Node<AnyType> = prev;
		public Node<AnyType> = next;

	public MyLinkedList( ) {
		clear( );}

	public void clear( ) // Change the size of this collection to zero.
		beginMarker = new Node<AnyType>( null, null, null ); 
		endMarker = new Node<AnyType>( null, beginMarker, null ); = endMarker;

		theSize = 0;

	public int size( ) { //Returns the number of items in this collection.
		return theSize; 

	public boolean isEmpty( ) { 
		return size( ) == 0;}

	public boolean add( AnyType x ) { //Adds an item to this collection, at the end
		add( size( ), x );
		return true;

	/* the add method adds an item to this collection, at specified position. * Items at or after that 	position are slid one position higher */

	public void add( int idx, AnyType x ) {
		addBefore( getNode( idx), x );}

	public AnyType get( int idx ) { // Returns the item at position idx
		return getNode( idx ).data;}

	public AnyType set( int idx, AnyType newVal ) { //Changes the item at position idx
		Node<AnyType> p = getNode( idx );
		AnyType oldVal =; = newVal; 
		return oldVal;

	public AnyType remove( int idx ) { //Removes an item from this collection
		return	remove(getNode( idx ));}

	/* this addBefore method adds an item to this collection, at specified position p. 
	Items at or after that position are slid one position higher */

	private void addBefore( Node<AnyType> p, AnyType x ) {
		Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p ); = newNode; 
		p.prev = newNode; 

	private AnyType remove( Node<AnyType> p ) {  // Removes the object contained in Node p. = p.prev; =; 

	private Node<AnyType> getNode( int idx)
		Node<AnyType> p;
		if( idx < 0 || idx > size() )
            throw new IndexOutOfBoundsException();
        if( idx < size( ) / 2 ) {
            p =;
            for( int i = 0; i < idx; i++ )
                p =;            
            p = endMarker;
            for( int i = size( ); i > idx; i-- )
                p = p.prev;
		return p;

	public java.util.Iterator<AnyType> iterator( ) {
        return new LinkedListIterator( );

	private class LinkedListIterator implements java.util.Iterator<AnyType>
		private Node<AnyType> current =;
       private int expectedModCount = modCount; 
		private boolean okToRemove = false;
		public boolean hasNext( ) {
			return current != endMarker;
        public AnyType next( )
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( ); 
            if( !hasNext( ) )
                throw new java.util.NoSuchElementException( ); 
            AnyType nextItem =;
            current =;
            okToRemove = true;
            return nextItem;
        public void remove( )
            if( modCount != expectedModCount )
                throw new java.util.ConcurrentModificationException( ); 
            if( !okToRemove )
                throw new IllegalStateException( );
            MyLinkedList.this.remove( current.prev );
            okToRemove = false;  

Open in new window

Question by:shampouya
    LVL 7

    Expert Comment

    Yes, you are true.
    This is a tipical structure of a linked list
    LVL 7

    Accepted Solution

    I mean that the minimal structure includes:
    the data
    a pointer to the next element
    a pointer to the previous element.

    In general formal definition of a linked list, there is no pointer to the previous element, but it helps a lot in browsing element.
    When you have a pointer to the previous element, it is named double linked list.
    See here for reference:

    Author Closing Comment


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Top 6 Sources for Identifying Threat Actor TTPs

    Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

    I guess that all of us know that caching the data usually increase the performance, but I worried if all of us are aware about the risk that caching the data provides and how to minimize this.  That’s the reason why I decided to write this short art…
    Using SQL Scripts we can save all the SQL queries as files that we use very frequently on our database later point of time. This is one of the feature present under SQL Workshop in Oracle Application Express.
    Video by: Steve
    Using examples as well as descriptions, step through each of the common simple join types, explaining differences in syntax, differences in expected outputs and showing how the queries run along with the actual outputs based upon a simple set of dem…
    Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

    759 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    11 Experts available now in Live!

    Get 1:1 Help Now