疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java数据结构---链表常用操作


 

  

  Java数据结构---链表常用操作

  今天写点Java数据结构中链表常用操作函数,包括很多操作,其中也包括很多在求职面试中会问到的一些试题,包括编程技巧。如果能仔细理解,体会下列算法相信一定会对自己的编程能力有所提高。比如:

  (1)//添加节点public Node addNode(int data)

  (2)//返回链表的长度public int length()

  (3)//删除指定位置的节点public boolean deleteNode(int index)

  (4)//对列表中的元素排序public Node orderLink()

  (5)//打印列表元素public void printLink()

  (6)//删除重复元素Method:1 public void delDuplecate()

  (7)//删除重复元素Method:2 public void delDup()

  一、链表节点的定义如下:

  package com.robin.Link;

  public class Node {

  public int data;

  public Node next = null;

  public Node(int data){

  this.data = data;

  }

  }

  二、链表常用操作如下:

  package com.robin.Link;

  import java.util.Hashtable;

  public class MyLink {

  static Node head = null;

  //添加节点

  public Node addNode(int data){

  Node newNode = new Node(data);

  if(head == null){

  head = newNode;

  return head;

  }

  Node temp = head;

  while(temp.next != null){

  temp = temp.next;

  }

  temp.next = newNode;

  return newNode;

  }

  //返回链表的长度

  public int length(){

  Node temp = head;

  int length = 0;

  while(temp != null){

  length++;

  temp = temp.next;

  }

  return length;

  }

  //删除指定位置的节点

  public boolean deleteNode(int index){

  if(index < 1 || index >length()){

  return false;

  }

  if(1 == index){

  head = head.next;

  return true;

  }

  Node preNode = head;

  Node curNode = preNode.next;

  int i=1;

  while(curNode != null){

  if( i == index){

  preNode = curNode.next;

  return true;

  }

  preNode = curNode;

  curNode = curNode.next;

  i++;

  }

  return true;

  }

  //对列表中的元素排序

  public Node orderLink(){

  Node preNode = head;

  Node curNode = null;

  while(preNode != null){

  curNode = preNode.next;

  while(curNode != null){

  if(preNode.data > curNode.data){

  int temp = curNode.data;

  curNode.data = preNode.data;

  preNode.data = temp;

  }

  curNode = curNode.next;

  }

  preNode = preNode.next;

  }

  return head;

  }

  //打印列表元素

  public void printLink(){

  Node temp = head;

  while(temp != null){

  System.out.print(temp.data + " ");

  temp = temp.next;

  }

  System.out.println();

  }

  //删除重复元素Method:1

  public void delDuplecate(){

  Hashtable

  Node temp = head;

  while(temp != null){

  if(hs.containsKey(temp.data)){

  temp = temp.next;

  }else{

  hs.put(temp.data, 1);

  }

  }

  }

  //删除重复元素Method:2

  public void delDup(){

  Node temp = head;

  while(temp != null){

  Node nextNode = temp;

  while(nextNode.next != null){

  if(temp.data == nextNode.next.data){

  nextNode.next = nextNode.next.next;

  }else{

  nextNode = nextNode.next;

  }

  }

  temp = temp.next;

  }

  }