single linked list

some examples available in internet开发者_开发问答 uses head and tail nodes for the single linked list and some examples doesn't why such differences are there.

A tail node make it O(1) to append an item to the end of the list, instead of having to iterate all the way from the head to find the tail before appending, making it an O(n) operation. It's therefore useful for efficiency, but not fundamentally required to make a usable list. I suspect the difference in examples is between academic purity and having a relatively useful list.

It would be utterly pointless to have a singly-linked list without remembering the head node though :)

The reason for keeping both head and tail is mainly speed when the lists needs to add new items to the end of the list.

Although it is trivial to find the end of the list it takes too much time compared to the effort it costs to keep track of it during list modifications.

The singly linked list uses less space - 1 less pointer per cell. It is also more efficient for adding to the head of the list and deleting from the first half of the list (fewer operations since don't need to maintain the other link).

The doubly linked list is more efficient for deleting or adding in the back half of the list.

In Lisp, which makes extensive use of lists, only singly linked lists are used. Actually, some implementations (like Symbolics) used arrays if the list was shorter than a certain length.

The choice of which to use depends on the application. If appending is a common operation, and speed is more important than space, then a doubly linked list may be appropriate. However, I think singly-linked list is more appropriate in most cases, and is thus more common.

As the others have pointed out, the tail reference provides a way to append a node to the end of the list in constant time. If your linked list implementation does not have a tail reference, you will have to iterate through all the nodes in the list in order to add it to the end. Below is a java Linked List example that uses 3 different methods for adding elements to a list.

• push(Node node) - adds the node to the beginning of the list. This takes constant time O(1) due to the head reference.
• add(int index, Node node) - adds the node at the specified index. This takes O(n) time since it has to iterate through each node until the correct index is found.

• add(Node node) - adds the node to the end of the list. As explained above, this operation only takes constant time since we are using a tail reference.

  // Insert element at the beginning of the list
  public void push(T _data) {
  
      Node<T> addNode = new Node<T>(_data);
  
      // Set head and tail to new pointer if list is empty
      if(this.head == null) {
          this.head = addNode;
          this.tail = addNode;
      } else {
          addNode.setNext(this.head); // Set new node's next pointer to the current head
          this.head = addNode;  // Set head to new node
      }
  
      this.numberNodes++;
  }
  
  // Insert element at the specified index
  public void add(int _index, T _data) {
  
      // Continue if _index is valid
      if(_index >= 0 && _index <= this.numberNodes) {
  
          if(_index == 0) { // Push element to front of list if _index is 0
              this.push(_data);
          } else if(_index == this.numberNodes) { // Add element to end of list if index is last element 
              this.add(_data);
          } else {
  
              // Continue if list is not empty
              if(this.head != null && this.tail != null) {
  
                  Node<T> addNode = new Node<T>(_data);
                  Node<T> currentNode = this.head.getNext();
                  Node<T> previousNode = this.head;
  
                  int count = 1;
                  while(currentNode != null) { // Traverse list to find element at _index
  
                      // Insert element when _index is found
                      if(count == _index) {
                          previousNode.setNext(addNode);
                          addNode.setNext(currentNode);
                          this.numberNodes++;
                          break;
                      }
  
                      // Prepare for next iteration
                      previousNode = currentNode;
                      currentNode = currentNode.getNext();
                      count++;
                  }   
              }
          }
      }
  }
  
  // Insert element at the end of the list
  public void add(T _data) {
  
      Node<T> addNode = new Node<T>(_data);
  
      // Set head and tail to new pointer if list is empty
      if(this.head == null) {
          this.head = addNode;
          this.tail = addNode;
      } else {
          this.tail.setNext(addNode); // Set tail's next pointer to new node
          this.tail = this.tail.getNext(); // Set tail to new node
      }
  
      this.numberNodes++;
  }
  

Adding the tail reference dramatically decreases the time to insert elements at the end of a Linked List. Take a look at my blog for Linked List implementations using tail references in Java, C++, Python, and JavaScript.