Java data structure (linear table) details

Linear table chain storage and implementation

Another method to achieve linear table is chain storage, that is, the pointer to store the data elements in the linear table in series of those units in 1. This approach avoids the disadvantage of storing elements in arrays in contiguous units, so when performing insert or delete operations, you no longer need to move the elements to make room or fill in the gaps. However, we pay the price of setting Pointers in each cell to represent the logical relationships between the elements in the table, thus incurring the overhead of additional storage space.

Singly linked lists

A linked list is a series of 1 cells that store data elements connected by a series of Pointers, so each cell has at least two fields, one for the storage of data elements and one for Pointers to other cells. A storage location with one data domain and multiple pointer domains is usually referred to as a node (node).

Node interface

package com.wjy.Data_Structure.linearlist.common;
public interface Node {
  /**
   *  Gets the node data domain 
   *
   * @return
   */
  public Object getData();
  /**
   *  Set the node data field 
   *
   * @param obj
   */
  public void setData(Object obj);
}

Single linked list node definition

package com.wjy.Data_Structure.linearlist.common;
// Single linked list node definition 
public class SLNode implements Node {
  private Object element;
  private SLNode next;
  public SLNode() {
  }
  public SLNode(Object ele, SLNode next) {
    this.element = ele;
    this.next = next;
  }
  public SLNode getNext() {
    return next;
  }
  public void setNext(SLNode next) {
    this.next = next;
  }
  /******** Methods of Node Interface **********/
  @Override
  public Object getData() {
    return element;
  }
  @Override
  public void setData(Object obj) {
    element = obj;
  }
}

Single linked list of linear tables

In the use of single linked list to achieve linear table, in order to make the program more concise, we usually in the single linked list before adding a dummy node, also known as the head node. In the header node, no substantial data object is stored, and its next field points to the node where element 0 is located in the linear table. The introduction of header node can make some boundary conditions in the linear table operation easier to deal with.

package com.wjy.Data_Structure.linearlist.listslinkimpl;
import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;
import com.wjy.Data_Structure.linearlist.common.List;
import com.wjy.Data_Structure.linearlist.common.SLNode;
import com.wjy.Data_Structure.linearlist.common.Strategy;
import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;
// Single linked list of linear tables 
public class ListSLinked implements List {
  private Strategy strategy; //  Data element comparison strategy 
  private SLNode head; //  The first node reference of a single linked list 
  private int size;//  The number of data elements in a linear table 
  public ListSLinked() {
    this(new DefaultStrategy());
  }
  public ListSLinked(Strategy strategy) {
    this.strategy = strategy;
    head = new SLNode();
    size = 0;
  }
  /**
   *  Auxiliary methods:   Get data elements  e  The precursor node of the node 
   *
   * @param e
   * @return
   */
  private SLNode getPreNode(Object e) {
    SLNode p = head;
    while (p.getNext() != null)
      if (strategy.equal(p.getNext().getData(), e))
        return p;
      else
        p = p.getNext();
    return null;
  }
  /**
   *  Auxiliary methods:   Get the sequence number is  0<=i<size  Is the precursor of the node where the element is located 
   *
   * @param i
   * @return
   */
  private SLNode getPreNode(int i) {
    SLNode p = head;
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }
  /**
   *  Auxiliary methods:   Get the sequence number is  0<=i<size  Is where the element is 
   *
   * @param i
   * @return
   */
  private SLNode getNode(int i) {
    SLNode p = head.getNext();
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }
  @Override
  public int getSize() {
    return size;
  }
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
  @Override
  public boolean contains(Object e) {
    return indexOf(e) != -1;
  }
  @Override
  public int indexOf(Object e) {
    SLNode p = head.getNext();
    int index = 0;
    while (p != null)
      if (strategy.equal(p.getData(), e)) {
        return index;
      } else {
        index++;
        p = p.getNext();
      }
    return -1;
  }
  @Override
  public void insert(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i > size)
      throw new OutOfBoundaryException(" Error. The specified insert number is out of bounds ");
    SLNode p = getPreNode(i);
    SLNode q = new SLNode(e, p.getNext());
    p.setNext(q);
    size++;
    return;
  }
  @Override
  public boolean insertBefore(Object obj, Object e) {
    SLNode p = getPreNode(obj);
    if (p != null) {
      SLNode q = new SLNode(e, p.getNext());
      p.setNext(q);
      size++;
      return true;
    }
    return false;
  }
  @Override
  public boolean insertAfter(Object obj, Object e) {
    SLNode p = head.getNext();
    while (p != null)
      if (strategy.equal(p.getData(), obj)) {
        SLNode q = new SLNode(e, p.getNext());
        p.setNext(q);
        size++;
        return true;
      } else {
        p = p.getNext();
      }
    return false;
  }
  @Override
  public Object remove(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException(" Error, the specified delete sequence number is out of bounds. ");
    SLNode p = getPreNode(i);
    Object obj = p.getNext().getData();
    p.setNext(p.getNext().getNext());
    size--;
    return obj;
  }
  @Override
  public boolean remove(Object e) {
    SLNode p = getPreNode(e);
    if (p != null) {
      p.setNext(p.getNext().getNext());
      size--;
      return true;
    }
    return false;
  }
  @Override
  public Object replace(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException(" Error, the specified serial number is out of bounds. ");
    SLNode p = getNode(i);
    Object obj = p.getData();
    p.setData(e);
    return obj;
  }
  @Override
  public Object get(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException(" Error, the specified serial number is out of bounds. ");
    SLNode p = getNode(i);
    return p.getData();
  }
}

Simple test cases

package com.wjy.Data_Structure.linearlist.listslinkimpl;
import org.junit.Test;
import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;
public class ListSLinkedTest {
  @Test
  public void testInsert() {
    ListSLinked list = new ListSLinked();
    for (int i = 0; i < 10; i++) {
      list.insert(i, i + 1);
    }
    System.out.println(" Delete: " + list.remove(0));
    System.out.println(list.contains(1));
    list.insertBefore(2, 100);
    list.insertAfter(2, 101);
    list.replace(list.getSize() - 1, 1000);
    for (int i = 0; i < list.getSize(); i++) {
      System.out.println(list.get(i));
    }
  }
}

Data structure learning code warehouse:

https://git.oschina.net/wjyonlyone/DataStructure