Java data structure (linear table) details
- 2020-06-01 09:47:10
- OfStack
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