链表:逻辑上连续,多个节点采用挂载的方式进行连接,物理上不连续.链表分为单链表和双链表.
一丶单链表①链表的实现(增删改查):
// 1、无头单向非循环链表实现
public class SinglelinkedList {
//头插法
public void addFirst(int val){
//尾插法
}
public void addLast(int val){
//任意位置插入,第一个数据节点为0号下标
}
public boolean addIndex(int index,int data){
//查找是否包含关键字key是否在单链表当中
}
public boolean contains(int key){
//删除第一次出现关键字为key的节点
}
public void remove(int key){
//删除所有值为key的节点
}
public void removeAllKey(int key){
}
}
②创建节点 :
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
具体代码实现:
package singallink;
public class SingallinkedList {
private int size;
private Node head;
public void addFirst(int val) {
Node node = new Node(val);
if(head == null){
head = node;
}else{
node.next = head;
head = node;
}
size++;
}
public void addIndex(int index,int val){
if(index < 0 || index > size){
System.out.println("add index illegal");
return;
}
if(index == 0){
addFirst(val);
return;
}
Node node = new Node(val);
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
node.next = prev.next;
prev.next = node;
size++;
}
public void addLast(int val){
addIndex(size,val);
}
public int seek(int index){
if(rangeCheck(index)){
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.val;
}else{
System.out.println("get index illegal");
return -1;
}
}
public boolean contains(int val){
for (Node i = head; i != null; i=i.next) {
if(i.val == val){
return true;
}
}
return false;
}
public int modify(int index,int newVal){
if(rangeCheck(index)){
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
int oldVal = node.val;
node.val = newVal;
return oldVal;
}else{
System.out.println("modify index illegal");
return -1;
}
}
public void removeIndex(int index){
if(rangeCheck(index)){
if(index == 0){
Node temp = head;
head = head.next;
temp.next = null;
size--;
}
Node prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node cur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
}else{
System.out.println("remove index illegal!");
}
}
public void removeFirst(){
removeIndex(0);
}
public void removeLast(){
removeIndex(size-1);
}
public void removevalonce(int val){
if(rangeCheck(val)){
if(head != null && head.val == val){
Node temp = head;
head = head.next;
temp.next = null;
size--;
}else{
Node prev = head;
while(prev.next != null){
if(prev.next.val == val){
Node cur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
return;
}
prev = prev.next;
}
}
}
}
public void removevalAll(int val){
while(head != null && head.val == val){
head = head.next;
size--;
}
if(head == null){
return;
}else{
Node prev = head;
while(prev.next != null){
if(prev.next.val == val){
Node cur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
}else{
prev = prev.next;
}
}
}
}
public boolean rangeCheck(int index){
if(index < 0 || index >= size){
return false;
}
return true;
}
public String toString(){
String ret = "";
Node node = head;
while(node != null){
ret+=node.val;
ret+="->";
node = node.next;
}
ret+="END";
return ret;
}
}
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
二丶双链表
①链表的实现:
public class DoublelinkedList {
//头插法
public void addFirst(int val){
}
//尾插法
public void addLast(int val){
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int val){
}
//查找值val是否在双链表当中
public boolean contains(int val){
}
//删除第一次出现值为val的节点
public void remove(int val){
}
//删除所有值为val的节点
public void removeAllval(int val){
}
}
②构造节点
class Node{
Node prev;
int val;
Node next;
public Node(int val) {
this.val = val;
}
public Node(Node prev, int val, Node next) {
this.prev = prev;
this.val = val;
this.next = next;
}
}
具体代码实现:
package doublelink;
public class DoublelinkedList {
private Node head;
private int size;
private Node tail;
public void addFirst(int val){
Node node = new Node(null,val,head);
if(head == null){
tail = node;
}else{
head.prev = node;
}
head = node;
size++;
}
public void addLast(int val){
Node node = new Node(tail,val,null);
if(tail == null){
head = node;
}else{
tail.next = node;
}
tail = node;
size++;
}
public void addIndex(int index,int val){
if(index < 0 ||index > size){
System.out.println("add index illegal!");
}else if(index == 0){
addFirst(val);
}else if(index == size){
addLast(val);
}else{
Node prev = node(index - 1);
Node newNode = new Node(prev,val,prev.next);
prev.next.prev = newNode;
prev.next = newNode;
size++;
}
}
public int get(int index){
if(rangeCheck(index)){
return node(index).val;
}else{
System.out.println("get index illegal!");
return -1;
}
}
private Node node (int index){
Node ret = null;
if(index < (size << 1)){
ret = head;
for (int i = 0; i < index; i++) {
ret = ret .next;
}
}else{
ret = tail;
for (int i = size-1; i > index; i--) {
ret = ret.prev;
}
}
return ret;
}
public boolean contains(int val){
for(Node x = head;x != null;x = x.next){
if(x.val == val){
return true;
}
}
return false;
}
public int set(int index,int newVal){
if(rangeCheck(index)){
Node node = node(index);
int oldVal = node.val;
node.val = newVal;
return oldVal;
}else{
System.err.println("set index illegal!");
return -1;
}
}
public void remove(int index){
if(rangeCheck(index)){
Node node = node(index);
unlink(node);
}else{
System.out.println("remove index illegal!");
}
}
public void removevalonce(int val){
for(Node x = head;x != null;x=x.next){
if(x.val == val){
unlink(x);
break;
}
}
}
public void removevalAll(int val){
for(Node x = head;x != null;){
if(x.val == val){
Node next = x.next;
unlink(x);
x = next;
}else{
x = x.next;
}
}
}
private void unlink(Node node){
Node prev = node.prev;
Node next = node.next;
if(prev == null){
head = next;
}else{
prev.next = node.next;
node.prev = null;
}
if(next == null){
tail = node.prev;
}else{
next.prev = prev;
node.next = null;
}
size--;
}
public boolean rangeCheck(int index){
if(index < 0 || index >= size){
return false;
}else{
return true;
}
}
public String toString(){
String ret = "";
Node node = head;
while(node != null){
ret += node.val + "->";
node = node.next;
}
ret += "END";
return ret;
}
}
class Node{
Node prev;
int val;
Node next;
public Node(int val) {
this.val = val;
}
public Node(Node prev, int val, Node next) {
this.prev = prev;
this.val = val;
this.next = next;
}
}
